Description

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$.

Input Format

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 Format

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

5
1 0
1 1
5 2
100 50
10000 5000

0
1
20
578028887
60695423

Hint

Constraints

This problem contains 20 test points, evenly divided. The constraints for each test point are shown in the table below.

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