{"raw_statement":[{"iden":"background","content":"提供了额外的 1 秒时限。"},{"iden":"statement","content":"有 $n$ 个格子排成一行，从左到右依次编号为 $1,2,\\cdots,n$，每个格子上有一个数字卡片，初始状态下，格子 $i$ 上的卡片数字为 $i$。\n\n打乱者会进行 $n$ 次交换操作来排列这些卡片：每次选择两个格子 $i,j$（$i\\ne j$），然后交换格子 $i$ 和格子 $j$ 上的卡片。$n$ 次交换操作结束后，就完成了对卡片的排列。\n\n然后轮到玩家行动，玩家同样需要用交换操作，每次交换两张卡片，目标是将这些卡片的顺序还原到初始状态。\n\n交换格子 $i$ 和格子 $j$ 上的卡片所需的时间为 $|i-j|$，玩家打算用最短的时间还原该排列。问：有多少种可能的排列，玩家可以用不超过 $m$ 的总时间完成还原？两种排列不同，当且仅当至少有一张数字卡片在两种排列中所在的格子不同。"},{"iden":"input","content":"每个测试点由多组数据组成。\n\n第一行包含一个正整数 $T$，表示数据组数。保证 $T\\le1,000$。\n\n之后 $T$ 行，每行一组数据，包含两个正整数 $n$，$m$。保证 $2\\le n\\le500$，$m\\le5,000$。\n"},{"iden":"output","content":"每组数据输出一行，一个整数表示答案。\n\n由于答案可能很大，请输出答案对 $1,000,000,007$ 取模的结果。\n"},{"iden":"note","content":"在第 $1$ 组数据中，打乱者的 $2$ 次操作均只可能是交换格子 $1$ 和格子 $2$ 上的卡片，只有 $1$ 种可能的排列，也就是初始状态 $[1,2]$。\n\n在第 $2$ 组数据中，有 $2$ 种可能的排列：$[1,3,2]$ 和 $[2,1,3]$。注意初始状态 $[1,2,3]$ 不是一种可能的排列，因为打乱者进行前 $2$ 次交换之后，所有卡片要么仍在初始状态（前 $2$ 次交换的是同一对卡片），要么均不在初始位置上（前 $2$ 次交换的不是同一对卡片），第 $3$ 次交换后不可能回到初始状态。\n\n在第 $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]$。\n\n**来源与致谢**\n\n来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。\n\n数据、题面、标程、题解等请参阅 THUPC 官方仓库 <https://thusaac.com/public>"}],"translated_statement":null,"sample_group":[["6\n2 1\n3 1\n5 2\n7 5\n10 20\n15 24\n","1\n2\n7\n331\n1570446\n73880648\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}