Find the number of permutations $A$ of length $n$ that satisfy the following conditions:
- The $n$ numbers from $1$ to $n$ each appear exactly once in the sequence.
- If the $i$-th number $A[i]$ has the value $i$, then $i$ is called a fixed point. The sequence has exactly $m$ fixed points.
Since there may be many such sequences, output the count modulo $10^9 + 7$.
Input
The first line contains an integer $T$, representing the number of test cases. Each of the next $T$ lines contains two integers $n$ and $m$.
Output
Output $T$ lines, each containing a single integer representing the number of sequences found.
Constraints
| $T$ | $n$ | $m$ |
|---|---|---|
| $1000$ | $\le 8$ | $\le 8$ |
| $1000$ | $\le 12$ | $\le 12$ |
| $1000$ | $\le 100$ | $\le 100$ |
| $1000$ | $\le 1000$ | $\le 1000$ |
| $500000$ | $\le 10000$ | $\le 10000$ |
Examples
Input 1
5 1 0 1 1 5 2 100 50 10000 5000
Output 1
0 1 20 578028887 60695423