题目描述
有 n 个格子排成一行,从左到右依次编号为 1,2,⋯,n,每个格子上有一个数字卡片,初始状态下,格子 i 上的卡片数字为 i。
打乱者会进行 n 次交换操作来排列这些卡片:每次选择两个格子 i,j(i≠j),然后交换格子 i 和格子 j 上的卡片。n 次交换操作结束后,就完成了对卡片的排列。
然后轮到玩家行动,玩家同样需要用交换操作,每次交换两张卡片,目标是将这些卡片的顺序还原到初始状态。
交换格子 i 和格子 j 上的卡片所需的时间为 |i−j|,玩家打算用最短的时间还原该排列。问:有多少种可能的排列,玩家可以用不超过 m 的总时间完成还原?两种排列不同,当且仅当至少有一张数字卡片在两种排列中所在的格子不同。
输入格式
从标准输入读入数据。
每个测试点由多组数据组成。
第一行包含一个正整数 T,表示数据组数。保证 T≤1,000。
之后 T 行,每行一组数据,包含两个正整数 n,m。保证 2≤n≤500,m≤5,000。
输出格式
输出到标准输出。
每组数据输出一行,一个整数表示答案。
由于答案可能很大,请输出答案对 1,000,000,007 取模的结果。
样例
输入
6
2 1
3 1
5 2
7 5
10 20
15 24
输出
1
2
7
331
1570446
73880648
解释
在第 1 组数据中,打乱者的 2 次操作均只可能是交换格子 1 和格子 2 上的卡片,只有 1 种可能的排列,也就是初始状态 [1,2]。
在第 2 组数据中,有 2 种可能的排列:[1,3,2] 和 [2,1,3]。注意初始状态 [1,2,3] 不是一种可能的排列,因为打乱者进行前 2 次交换之后,所有卡片要么仍在初始状态(前 2 次交换的是同一对卡片),要么均不在初始位置上(前 2 次交换的不是同一对卡片),第 3 次交换后不可能回到初始状态。
在第 3 组数据中,有 7 种可能的排列:[1,2,3,5,4],[1,2,4,3,5],[1,2,5,4,3],[1,3,2,4,5],[1,4,3,2,5],[2,1,3,4,5],[3,2,1,4,5]。