Problem Description

Define two permutations $A$ and $B$ of length $n$ to be similar if, for all $i$, $C(A, A_i) = C(B, B_i)$ holds. Here, $C(P, x)$ is the number of indices $j$ such that $P_j < x$ $(1 \leqslant j \leqslant n)$.

For two permutations $P_1, P_2$ of length $n$, define the function $F(P_1, P_2)$ as the number of pairs $(l, r)$ such that $P_1[l \ldots r]$ is similar to $P_2[l \ldots r]$ $(1 \leqslant l \leqslant r \leqslant n)$, and $P_1[l \ldots r]$ contains no more than $E$ inversion pairs.

Now you need to compute: after letting $P_1$ and $P_2$ range over all permutations of $1 \sim n$, the sum of all $F(P_1, P_2)$.

Input Format

The first line contains an integer $T$, which denotes the number of test cases.

The next $T$ lines each contain two non-negative integers $n, E$.

Output Format

For each test case, output one integer per line, which is the answer modulo $10^9 + 7$.

4
2 2
2 1
2 0
1 1

10
10
9
1

Hint

For $50\%$ of the testdata, $T \leqslant 10^4, n \leqslant 10, E \leqslant 50$.

For $80\%$ of the testdata, $T \leqslant 10^4, n \leqslant 50, E \leqslant 10^6$.

For $100\%$ of the testdata, $T \leqslant 10^4, n \leqslant 500, E \leqslant 10^6$.

Translated by ChatGPT 5