CF1704H1.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$.

这是本题的简单版本。简单版与困难版的区别在于对 $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$ 的排列是指一个长度为 $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$ 取模的结果。

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$.

唯一的一行包含两个正整数 $k$ 和 $M$（$1\le k\le 5000$，$2\le M\le 10^9$）。保证 $2^{18}$ 是 $M-1$ 的约数，且 $M$ 是一个质数。

你需要计算 $n=k$ 时的答案。

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

输出一个整数——当 $n=k$ 时，不同序列对的数目对 $M$ 取模的结果。

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$.

当 $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])$）。