题目描述

There is a classic way to remove an element from an array: swap the values of the element to be removed and the last element of the array, and then delete the last element. Unfortunately, it turned out that this method does not always preserve the order of the elements in the array. Your task is to count the number of sequences of $k$ deletions after which the initially sorted array in ascending order will remain sorted.

You are given an array $a$ of length $n$, initially filled with numbers from $1$ to $n$ in ascending order, that is, $a_i=i$, and an array $b$ of length $k$, whose elements are pairwise distinct numbers from $1$ to $n$.

There are $k$ steps performed, at the $j$-th step the following occurs: an index $i$ is chosen from $1$ to $n-j+1$ such that $a_i=b_j$, after which $a_i$ and $a_{n-j+1}$ are swapped (if $i=n-j+1$, nothing happens). Then the last element of the array at this step, which has the index $n - j + 1$, is removed from the array.

The array $[b_1,b_2,\ldots,b_k]$ is called $\textit{good}$ if after performing $k$ steps the array $[a_1,a_2,\ldots,a_{n-k}]$ is strictly increasing.

You are given the numbers $n$ and $k$, count the number of good arrays $[b_1,b_2,\ldots,b_k]$. The answer may be too large, so output the remainder of the answer when divided by $10^9+7$.

输入格式

The first line contains an integer $t$ ($1 \le t \le 10^4$) --- the number of test cases. In the following $t$ lines, the test cases are provided.

In the first line of each test case, the integers $n$ and $k$ are given ($1 \le n \le 5\cdot 10^5$, $0 \le k \le n$).

It is guaranteed that the sum of $n$ across all test cases does not exceed $5\cdot 10^5$.

输出格式

For each test case, output a single integer --- the number of good arrays $b$, taken modulo $10^9+7$.

5
1 0
1 1
2 2
3 1
4 2

1
1
2
2
7

提示

Let's analyze the fourth test from the example. In it, $n=3$ and $k=1$. Initially, $a=[1,2,3]$. Let's see how $a$ changes after the first step for all possible arrays $b$.

• $b=[1]$. Then $a$ changes as follows: $[1, 2, 3]\to[3,2,1]\to[3,2]$. The array $[3,2]$ is not increasing.
• $b=[2]$. Then $a$ changes as follows: $[1, 2, 3]\to[1,3,2]\to[1,3]$. The array $[1,3]$ is increasing.
• $b=[3]$. Then $a$ changes as follows: $[1, 2, 3]\to[1,2,3]\to[1,2]$. The array $[1,2]$ is increasing.

We find that there are two good arrays $b=[2]$ and $b=[3]$, so the answer to the fourth test from the example is $2$.