408144: GYM102994 I A Math Problem

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. A Math Problemtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

There are $$$n$$$ fans $$$F_i(i=1,\cdots,n)$$$ and $$$m$$$ teams $$$T_j(j=1,\cdots,m)$$$.

(i) For any fan $$$F_i$$$, $$$F_i$$$ is a fan of at least one team but not a fan of all teams.

(ii) For any two teams $$$T_{i}, T_{j}$$$($$$1 \leq i,j \leq m$$$), there exists exactly one team $$$T_{k}$$$($$$1 \leq k \leq m$$$) exactly having the fans both $$$T_{i}$$$ and $$$T_{j}$$$ have. Note that $$$i,j,k$$$ can be the same.

(iii) For any two teams $$$T_{i}, T_{j}$$$($$$1 \leq i,j \leq m$$$), there exists exactly one team $$$T_{k}$$$($$$1 \leq k \leq m$$$) exactly having the fans either $$$T_{i}$$$ or $$$T_{j}$$$ have. Note that $$$i,j,k$$$ can be the same.

Please calculate that How many kinds of correspondences between the fans and the teams.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$($$$T \leq 100000$$$), indicating the number of test cases. For each test case:

The first and only line contains two integers $$$n,m(1\leq n\leq10^{18},2\leq m\leq6)$$$.

Output

For each test case, output a integer representing the answer modulo $$$1000000007(10^9+7)$$$ in one line.

ExampleInput
9
2 2
2 3
3 3
3 4
4 4
4 5
5 5
5 6
6 6
Output
2
12
36
216
1032
7200
46800
453600
3369600

加入题单

上一题 下一题 算法标签: