Game of AI (easy version)

题目描述

This is the easy version of this problem. The difference between easy and hard versions is the constraint on $ k $ and the time limit. Also, in this version of the problem, you only need to calculate the answer when $ n=k $ . You can make hacks only if both versions of the problem are solved. Cirno is playing a war simulator game with $ n $ towers (numbered from $ 1 $ to $ n $ ) and $ n $ bots (numbered from $ 1 $ to $ n $ ). The $ i $ -th tower is initially occupied by the $ i $ -th bot for $ 1 \le i \le n $ . Before the game, Cirno first chooses a permutation $ p = [p_1, p_2, \ldots, p_n] $ of length $ n $ (A permutation of length $ n $ is an array of length $ n $ where each integer between $ 1 $ and $ n $ appears exactly once). After that, she can choose a sequence $ a = [a_1, a_2, \ldots, a_n] $ ( $ 1 \le a_i \le n $ and $ a_i \ne i $ for all $ 1 \le i \le n $ ). The game has $ n $ rounds of attacks. In the $ i $ -th round, if the $ p_i $ -th bot is still in the game, it will begin its attack, and as the result the $ a_{p_i} $ -th tower becomes occupied by the $ p_i $ -th bot; the bot that previously occupied the $ a_{p_i} $ -th tower will no longer occupy it. If the $ p_i $ -th bot is not in the game, nothing will happen in this round. After each round, if a bot doesn't occupy any towers, it will be eliminated and leave the game. Please note that no tower can be occupied by more than one bot, but one bot can occupy more than one tower during the game. At the end of the game, Cirno will record the result as a sequence $ b = [b_1, b_2, \ldots, b_n] $ , where $ b_i $ is the number of the bot that occupies the $ i $ -th tower at the end of the game. However, as a mathematics master, she wants you to solve the following counting problem instead of playing games: Count the number of different pairs of sequences $ a $ and $ b $ that we can get from all possible choices of sequence $ a $ and permutation $ p $ . Since this number may be large, output it modulo $ M $ .

输入输出格式

输入格式

The only line contains two positive integers $ k $ and $ M $ ( $ 1\le k\le 5000 $ , $ 2\le M\le 10^9 $ ). It is guaranteed that $ 2^{18} $ is a divisor of $ M-1 $ and $ M $ is a prime number. You need to calculate the answer for $ n=k $ .

输出格式

Output a single integer — the number of different pairs of sequences for $ n=k $ modulo $ M $ .

输入输出样例

输入样例 #1

1 998244353

输出样例 #1

0

输入样例 #2

2 998244353

输出样例 #2

2

输入样例 #3

3 998244353

输出样例 #3

24

输入样例 #4

8 998244353

输出样例 #4

123391016

说明

For $ n=1 $ , no valid sequence $ a $ exists. We regard the answer as $ 0 $ . For $ n=2 $ , there is only one possible array $ a $ : $ [2, 1] $ . - For array $ a $ is $ [2, 1] $ and permutation $ p $ is $ [1, 2] $ , the sequence $ b $ will be $ [1, 1] $ after all rounds have finished. The details for each rounds: - In the first round, the first bot will begin its attack and successfully capture the tower $ 2 $ . After this round, the second bot will be eliminated and leave the game as all of its towers are occupied by other bots. - In the second round, the second bot is not in the game. - For array $ a $ is $ [2, 1] $ and permutation $ p $ is $ [2, 1] $ , the sequence $ b $ will be $ [2, 2] $ after all rounds have finished. The details for each rounds: - In the first round, the second bot will begin its attack and successfully capture the tower $ 1 $ . After this round, the first bot will be eliminated and leave the game as all of its towers are occupied by other bots. - In the second round, the first bot is not in the game. So the number of different pairs of sequences $ (a,b) $ is $ 2 $ ( $ [2, 1] $ , $ [1, 1] $ and $ [2, 1] $ , $ [2, 2] $ ) for $ n=2 $ .

题目大意：这是一个简化版的问题，与困难版本的主要区别在于对 $ k $ 的限制和时间限制。在这个版本中，您只需要计算 $ n=k $ 时的答案。如果两个版本的问题都解决了，您可以进行攻击。

Cirno 正在玩一个战争模拟游戏，有 $ n $ 座塔（编号从 1 到 $ n $）和 $ n $ 个机器人（编号从 1 到 $ n $）。初始时，第 $ i $ 座塔被第 $ i $ 个机器人占领。

在游戏开始前，Cirno 首先选择一个长度为 $ 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 $ 且对所有 $ 1 \le i \le n $ 有 $ a_i \ne i $）。

游戏有 $ 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 $ 为模输出它。

输入输出格式：

输入格式：输入只有一行，包含两个正整数 $ 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]）。题目大意：这是一个简化版的问题，与困难版本的主要区别在于对 $ k $ 的限制和时间限制。在这个版本中，您只需要计算 $ n=k $ 时的答案。如果两个版本的问题都解决了，您可以进行攻击。 Cirno 正在玩一个战争模拟游戏，有 $ n $ 座塔（编号从 1 到 $ n $）和 $ n $ 个机器人（编号从 1 到 $ n $）。初始时，第 $ i $ 座塔被第 $ i $ 个机器人占领。 在游戏开始前，Cirno 首先选择一个长度为 $ 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 $ 且对所有 $ 1 \le i \le n $ 有 $ a_i \ne i $）。 游戏有 $ 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 $ 为模输出它。 输入输出格式： 输入格式：输入只有一行，包含两个正整数 $ 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]）。