Description

On Valentine’s Day, $\color{orange}\texttt{Biadocy}$ was treated very badly, especially when an upper-class duke and a child said something like “Every day with you is Valentine’s Day.” So he found a chance to take revenge.

Now there are $n$ couples numbered $1 \sim n$ standing in a line in an arbitrary order. $\color{orange}\texttt{Biadocy}$ runs the following sorting pseudocode on them.

$\color{orange}\texttt{Biadocy}$ wants to know how many initial permutations will result in the couples’ numbers being in increasing order after being processed by this pseudocode. Maybe this will make him feel a bit better.

Input Format

The first line contains an integer $T$, the number of test cases.

The next $T$ lines each contain two integers $n, k$, representing the number of couples and the parameter passed in the first call to the pseudocode.

Output Format

Output $T$ lines. Each line contains one integer: the answer modulo $10^9+7$.

3
3 1
10 2
1 0

3
25200
1

5
502520 0
502520 1
502520 2
502520 3
502520 4

1
218102685
429650441
770595802
584122358

Hint

For the first $10\%$ of the testdata, $T=0$.
For the first $30\%$ of the testdata, $T\leq 10$, $n\leq 7$.
For another $10\%$ of the testdata, $k=0$.
For another $10\%$ of the testdata, $k=100$.
For $100\%$ of the testdata, $0\leq T\leq 10^5$, $1\leq n\leq 10^6$, $0\leq k\leq 100$.

Translated by ChatGPT 5