题目描述

定义两个长为 $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$。

4
2 2
2 1
2 0
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$。