Game of AI (easy version)
Contest: CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 3200
Tags: combinatorics, constructive algorithms, dp, fft, math

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

Input format:
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 format:
Output a single integer — the number of different pairs of sequences for $$$n=k$$$ modulo $$$M$$$.

Constraints:
Time limit: 2.5 s
Memory limit: 1024.0 MB

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

Example input:
1 998244353

Example output:
0

Example input:
2 998244353

Example output:
2

Editorial:
Consider calculate the number of possible sequences $$$a$$$ for a fixed sequence $$$b$$$.
We can find that if $$$b_i\ne i$$$, that means $$$i$$$ is occupied by $$$b_i$$$ finally, so we have $$$a_{b_i}$$$=i. If $$$b_i=i$$$, that means for all $$$j$$$ that $$$a_j=i$$$, $$$j$$$ is occupied before it begins its attack. As a result, we must have $$$b_j\ne j$$$.
The sequences $$$a$$$ which satisfies the above conditions is also possible to match a valid $$$p$$$. The attacking order can be arranged easily.
Now for how to count, we can build a graph according to the information given by $$$b_i\ne i$$$. We can see that the graph will in the form of some chains. Also, we can find that for a graph which consists of some chains, we can find the unique $$$b$$$ which satisfies the graph. Then some positions of array $$$a$$$ is also fixed, except the top of each chain. As for how to decide the these $$$a_i$$$($$$i$$$ is the top of some chain), we need to divide into two situations: one is the chain's length is greater than $$$1$$$, we can see that this $$$a_i$$$ can take any number between $$$1$$$ and $$$n$$$ except $$$i$$$; The other one is the chain's length is one, so $$$a_i$$$ cannot be any bottom of each chain. Then we can easily calculate the number of arrays $$$a$$$ by product the possible number of values of each $$$a_i$$$.
In conclusion, we can enumerate the number of chains, and the number of chains with length $$$1$$$, then use combination number to calculate. Time complexity is $$$O(n^2)$$$.