这是这个问题的简单版本。简单版和困难版的区别在于$$$k$$$ 的限制和时间限制。另外,在这个版本的问题中,您只需计算 $$$n=k$$$ 时的答案。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。
Cirno 正在玩一款战争模拟器游戏,其中有 $$$n$$$ 塔(编号从 $$$1$$$ 到 $$$n$$$)和 $$$n$$$ 机器人(编号从 $$$1$$$ 到 $$$n$$$)。第 $$$i$$$ 个塔最初被第 $$$i$$$ 个机器人占据 $$$1 \le i \le n$$$。
比赛前,琪露诺首先选择一个长度为$$$n$$$的排列$$$p = [p_1, p_2, \ldots, p_n]$$$(长度为$$$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$$$-th 轮中,如果第 $$$p_i$$$-th 机器人仍在游戏中,它将开始攻击,结果 $$$a_{p_i}$$$-th 塔被第 $$$p_i$$$-th 机器人占领;之前占据第 $$$a_{p_i}$$$ 塔的机器人将不再占据它。如果第 $$$p_i$$$ 个机器人不在游戏中,则本轮不会发生任何事情。
每轮结束后,如果机器人没有占领任何塔,它将被淘汰并离开游戏。请注意,任何塔都不能被多于一个机器人占据,但在游戏过程中一个机器人可以占据多于一塔。
游戏结束时,Cirno 会将结果记录为序列 $$$b = [b_1, b_2, \ldots, b_n]$$$,其中 $$$b_i$$$ 是游戏结束时占领第 $$$i$$$ 塔的机器人编号。
然而,作为一名数学大师,她希望你解决以下计数问题,而不是玩游戏:
计算我们可以从序列 $$$a$$$ 和排列 $$$p$$$ 的所有可能选择中得到的不同序列对 $$$a$$$ 和 $$$b$$$ 的数量。
由于这个数字可能很大,因此输出它对 $$$M$$$ 取模。
输入
唯一的一行包含两个正整数 $$$k$$$ 和 $$$M$$$ ($$$1\le k\le 5000$$$, $$$2\le M\le 10^9$$$ )。保证 $$$2^{18}$$$ 是 $$$M-1$$$ 的约数,并且 $$$M$$$ 是素数。
您需要计算 $$$n=k$$$ 的答案。
输出
输出一个整数 — $$$n=k$$$ 模 $$$M$$$ 的不同序列对的数量。
示例
输入 #1
1 998244353
输出 #1
0
输入 #2
2 998244353
输出 #2
2
输入 #3
3 998244353
输出 #3
24
输入#4
8 998244353
输出#4
123391016
注意
对于 $$$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]$$$)。