{"problem":{"name":"[THUPC 2024 决赛] 排列游戏","description":{"content":"有 $n$ 个格子排成一行，从左到右依次编号为 $1,2,\\cdots,n$，每个格子上有一个数字卡片，初始状态下，格子 $i$ 上的卡片数字为 $i$。 打乱者会进行 $n$ 次交换操作来排列这些卡片：每次选择两个格子 $i,j$（$i\\ne j$），然后交换格子 $i$ 和格子 $j$ 上的卡片。$n$ 次交换操作结束后，就完成了对卡片的排列。 然后轮到玩家行动，玩家同样需要用交换操作，每","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3500,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10547"},"statements":[{"statement_type":"Markdown","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$ 的总时间完成还原？两种排列不同，当且仅当至少有一张数字卡片在两种排列中所在的格子不同。\n\n## Input\n\n每个测试点由多组数据组成。\n\n第一行包含一个正整数 $T$，表示数据组数。保证 $T\\le1,000$。\n\n之后 $T$ 行，每行一组数据，包含两个正整数 $n$，$m$。保证 $2\\le n\\le500$，$m\\le5,000$。\n\n## Output\n\n每组数据输出一行，一个整数表示答案。\n\n由于答案可能很大，请输出答案对 $1,000,000,007$ 取模的结果。\n\n[samples]\n\n## Background\n\n提供了额外的 1 秒时限。\n\n## Note\n\n在第 $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>","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10547","tags":["2024","THUPC"],"sample_group":[["6\n2 1\n3 1\n5 2\n7 5\n10 20\n15 24\n","1\n2\n7\n331\n1570446\n73880648\n"]],"created_at":"2026-03-03 11:09:25"}}