시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 256 MB111100.000%

## 문제

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.

## 예제 입력 1

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


## 예제 출력 1

2
12
36
216
1032
7200
46800
453600
3369600