[FJWC2018] 全排列
题目描述
定义两个长为 $n$ 的排列 $A$ 与 $B$ 相似:若 $\forall i$,满足 $C(A, A_i) = C(B, B_i)$。其中 $C(P, x)$ 为满足 $P_j < x$ $(1 \leqslant j \leqslant n)$ 的 $j$ 的数目。
对于两个长为 $n$ 的排列 $P_1, P_2$,定义函数 $F(P_1, P_2)$ 等于满足 $P_1[l \ldots r]$ 相似于 $P_2[l \ldots r]$ $(1 \leqslant l \leqslant r \leqslant n)$ 并且 $P_1[l \ldots r]$ 包含不超过 $E$ 个逆序对的数对 $(l, r)$ 的数目。
现在请你求出:对 $P_1, P_2$ 分别取遍所有 $1 \sim n$ 的排列后所有 $F(P_1, P_2)$ 的和。
输入输出格式
输入格式
第一行一个整数 $T$ 表示数据组数。
接下来 $T$ 行,每行包含两个非负整数 $n, E$。
输出格式
对于每组数据,输出一行一个整数表示答案模 $10^9 + 7$。
输入输出样例
输入样例 #1
4
2 2
2 1
2 0
1 1
输出样例 #1
10
10
9
1
说明
对于 $50\%$ 的数据,$T \leqslant 10^4, n \leqslant 10, E \leqslant 50$。
对于 $80\%$ 的数据,$T \leqslant 10^4, n \leqslant 50, E \leqslant 10^6$。
对于 $100\%$ 的数据,$T \leqslant 10^4, n \leqslant 500, E \leqslant 10^6$。