题目描述

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

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

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

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

输入格式

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

第一行包含一个正整数 $T$，表示数据组数。保证 $T\le1,000$。

之后 $T$ 行，每行一组数据，包含两个正整数 $n$，$m$。保证 $2\le n\le500$，$m\le5,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]$。

来源与致谢

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。

数据、题面、标程、题解等请参阅 THUPC 官方仓库 https://thusaac.com/public