P4678 [FJWC2018] Full Permutation

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

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

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

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