Subpermutation

A permutation of $n$ is a sequence of length $n$ in which each number from $1$ to $n$ appears exactly once. A $\textit{full-permutation}$ of $n$ is a sequence that connects all permutations of $n$ into one sequence in lexicographical order. Sequence $p_1, p_2, \dots, p_n$ is lexicographically smaller than $q_1, q_2, \dots, q_n$ if $p_i \lt q_i$ where $i$ is the minimum index satisfying $p_i \neq q_i$.

Here are some symbols used in this problem:

- $p_n$: the full-permutation of $n$. For example, $p_3 = \{1,2,3,1,3,2,2,1,3,2,3,1,3,1,2,3,2,1\}$ .
- $S_n$: the set of all permutations of $n$. For example, $S_3=\{\{1,2,3\},\{1,3,2\},\{2,1,3\},\{2,3,1\},\{3,1,2\},\{3,2,1\}\}$.
- $f(s,t)$: the number of contiguous subsequences in $s$ that are equal to $t$. For example, $f(\{1,2,12,1,2\},\{1,2\})=2$.

Now given $n$ and $m$, please calculate $\sum_{t\in{S_m}}f(p_n,t)$ modulo $10^9+7$.

The first line contains one integer $T\ (1\le T\le 10^5)$, indicating the number of test cases.

The only line for each case contains two integers $n\ (1\le n\le 10^6)$ and $m\ (1\le m\le n)$, as described in the description.

For each test case, output a single integer $\sum_{t\in{S_m}}f(p_n,t)$ modulo $10^9+7$.

4
2 1
2 2
3 2
4 3

2
2
4
15

For the third case in the sample, $p_3 = \{1,2,3,1,3,2,2,1,3,2,3,1,3,1,2,3,2,1\}$, $S_2=\{\{1,2\},\{2,1\}\}$. There are $4$ contiguous subsequences in $p_3$ that are equal to $\{1,2\}$ or $\{2,1\}$: $\{\underline{1,2},3,1,3,2,\underline{2,1},3,2,3,1,3,\underline{1,2},3,\underline{2,1}\}$.

2021中国大学生程序设计竞赛（CCPC）- 网络选拔赛（重赛）