#5255. [Fjwc2018]全排列

内存限制:512 MiB 时间限制:10 Sec

题目描述

定义两个长为n的排列A与B相似:若?i,满足C(A, Ai) = C(B, Bi)。其中C(P, x)为满足
Pj < x(1 ≤ j ≤ n)的j的数目。
对于两个常委n的排列P1,P2,定义函数F(P1,P2)等于满足P1[l . . . r] 相似于
P2[l . . . r](1 ≤ l ≤r ≤ n)并且P1[l . . . r]包含不超过E个逆序对的数对(l,r)的数目。
现在请你求出:对P1,P2分别取遍所有1~n的排列后所有F(P1,P2)的和

输入格式

第一行一个整数T表示数据组数。
接下来T行每行两个非负整数n,E。
T ≤ 10^4, n ≤ 500, E ≤ 10^6

输出格式

对于每组数据输出一行一个整数表示答案,答案对1e9+7取模。

样例

样例输入


			
4
2 2
2 1
2 0
1 1

样例输出


			
10
10
9
1

数据范围与提示