QOJ.ac

QOJ

Time Limit: 2.5 s Memory Limit: 512 MB
[+6]

# 8746. 排列游戏

Statistics

题目描述

n 个格子排成一行,从左到右依次编号为 1,2,,n,每个格子上有一个数字卡片,初始状态下,格子 i 上的卡片数字为 i

打乱者会进行 n 次交换操作来排列这些卡片:每次选择两个格子 i,jij),然后交换格子 i 和格子 j 上的卡片。n 次交换操作结束后,就完成了对卡片的排列。

然后轮到玩家行动,玩家同样需要用交换操作,每次交换两张卡片,目标是将这些卡片的顺序还原到初始状态。

交换格子 i 和格子 j 上的卡片所需的时间为 |ij|,玩家打算用最短的时间还原该排列。问:有多少种可能的排列,玩家可以用不超过 m 的总时间完成还原?两种排列不同,当且仅当至少有一张数字卡片在两种排列中所在的格子不同。

输入格式

从标准输入读入数据。

每个测试点由多组数据组成。

第一行包含一个正整数 T,表示数据组数。保证 T1,000

之后 T 行,每行一组数据,包含两个正整数 nm。保证 2n500m5,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]