Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4084
Little Sub and Heltion's Math Problem

Time Limit: 1 Second      Memory Limit: 262144 KB

Little Sub has a friend called Heltion. When he knows that Mr.Potato has given a hard Math problem to Little Sub, he decides to help Little Sub fight back. Therefore, along with Little Sub, Heltion locks Mr.Potato's fridge with an electronic lock, which requires a password to open. Then Heltion leaves a message to Mr.Potato: "The password is the answer to this easy Math problem. Please solve it."

“math”/

Well, Mr.Potato cannot solve this Math problem. Please help him.

There are $n$ fans $F_1, F_2, \dots, F_n$ and $m$ teams $T_1, T_2, \dots, T_m$.

  1. For any fan $F_i$, $F_i$ is a fan of at least one team but not a fan of all teams;
  2. 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;
  3. 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 tell Mr.Potato that the number of ways relating the fans to the teams satisfying the restrictions above. Two ways are considered different if there exists a team such that this team has different sets of fans in these two ways.

Input

There are multiple test cases. The first line of the input contains an integer $T$($1 \le T \le 10^5$), indicating the number of test cases. For each test case:

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

Output

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

Sample Input

9
2 2
2 3
3 3
3 4
4 4
4 5
5 5
5 6
6 6

Sample Output

2
12
36
216
1032
7200
46800
453600
3369600

Note

For the first sample case, there are $2$ ways relating the fans to the teams:

  1. $F_1$ is a fan of $T_1$ and $F_2$ is a fan of $T_1$;
  2. $F_1$ is a fan of $T_2$ and $F_2$ is a fan of $T_2$.


Author: LYU, Yaowei
Source: ZOJ Monthly, January 2019
Submit    Status