I. A Math Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard 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.

Example
Input
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