23554번 - A Math Problem 다국어

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.

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)$.

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