P4071 [SDOI2016] Permutation Counting

Count the number of permutations $a$ of $1$ to $n$ such that there are exactly $m$ positions $i$ with $a_i = i$. Output the answer modulo $10^9 + 7$.

**There are multiple test cases in a single test file.** The first line contains an integer $T$, representing the number of test cases. The following $T$ lines each describe one test case. For each test case, a single line contains two integers $n$ and $m$, in that order.

Output $T$ lines. For each test case, output one integer representing the answer.

#### Constraints This problem contains 20 test points, evenly divided. The constraints for each test point are shown in the table below. | Test point ID | $T =$ | $n, m \leq$ | Test point ID | $T =$ | $n, m \leq$ | | :-----------: | :----: | :---------: | :-------------: | :-------------: | :---------: | | $1 \sim 3$ | $10^3$ | $8$ | $10 \sim 12$ | $10^3$ | $10^3$ | | $4 \sim 6$ | $10^3$ | $12$ | $13 \sim 14$ | $5 \times 10^5$ | $10^3$ | | $7 \sim 9$ | $10^3$ | $100$ | $15 \sim 20$ | $5 \times 10^5$ | $10^6$ | For all test points, it is guaranteed that $1 \leq T \leq 5 \times 10^5$, $1 \leq n \leq 10^6$, $0 \leq m \leq 10^6$. Translated by ChatGPT 5