P7392 "TOCO Round 1" Strange Sorting.

Joy does not ask the heavens, romance does not ask the heavens, gentleness does not ask the heavens, good times do not ask the heavens, good fate does not ask the heavens. You do not ask the heavens.

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.

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 $T$ lines. Each line contains one integer: the answer modulo $10^9+7$.

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