CF1704H1 Game of AI (easy version)

这是本题的简单版本。简单版本与困难版本的区别在于对 $k$ 的约束和时间限制。此外，在本版本中，你只需要计算 $n=k$ 时的答案。只有当两个版本均被解决时，你才能进行 hack。 Cirno 正在玩一款战争模拟游戏，其中有 $n$ 座塔（编号为 $1$ 至 $n$）和 $n$ 个机器人（编号为 $1$ 至 $n$）。初始时，第 $i$ 座塔被第 $i$ 个机器人占据（$1 \le i \le n$）。 在游戏开始前，Cirno 首先选择一个长度为 $n$ 的排列 $p = [p_1, p_2, \ldots, p_n]$（一个长度为 $n$ 的排列是指每个 $1$ 到 $n$ 的整数恰好出现一次的数组）。接着，她选择一个序列 $a = [a_1, a_2, \ldots, a_n]$（满足 $1 \le a_i \le n$ 且 $a_i \ne i$ 对所有 $1 \le i \le n$ 成立）。 游戏包含 $n$ 轮攻击。在第 $i$ 轮中，如果第 $p_i$ 个机器人仍在游戏中，它将发起攻击，导致第 $a_{p_i}$ 座塔被第 $p_i$ 个机器人占据；原本占据第 $a_{p_i}$ 座塔的机器人将失去该塔。如果第 $p_i$ 个机器人已不在游戏中，此轮不会发生任何事。 每轮结束后，如果一个机器人未占据任何塔，它将被淘汰并退出游戏。注意一座塔不能同时被多个机器人占据，但一个机器人可以在游戏中占据多座塔。 游戏结束时，Cirno 将记录结果序列 $b = [b_1, b_2, \ldots, b_n]$，其中 $b_i$ 表示结束时占据第 $i$ 座塔的机器人编号。 然而，作为数学大师，她希望你解决以下计数问题而非亲自游戏： 计算所有可能的序列 $a$ 和排列 $p$ 能生成的不同序列对 $(a, b)$ 的数量。 由于结果可能很大，请输出其对 $M$ 取模后的值。

无

无

当 $n=1$ 时，不存在合法的序列 $a$，因此答案为 $0$。 当 $n=2$ 时，唯一可能的数组 $a$ 是 $[2, 1]$： - 当 $a$ 为 $[2, 1]$ 且 $p$ 为 $[1, 2]$ 时，最终序列 $b$ 为 $[1, 1]$。具体过程： - 第一轮，第一个机器人发起攻击并占领第 $2$ 座塔。此轮结束后，第二个机器人因失去所有塔而被淘汰。 - 第二轮，第二个机器人已不在游戏中。 - 当 $a$ 为 $[2, 1]$ 且 $p$ 为 $[2, 1]$ 时，最终序列 $b$ 为 $[2, 2]$。具体过程： - 第一轮，第二个机器人发起攻击并占领第 $1$ 座塔。此轮结束后，第一个机器人被淘汰。 - 第二轮，第一个机器人已不在游戏中。 因此当 $n=2$ 时，不同的序列对 $(a, b)$ 的数量为 $2$（即 $([2, 1], [1, 1])$ 和 $([2, 1], [2, 2])$）。 翻译由 DeepSeek R1 完成