CF1764D.Doremy's Pegging Game

Doremy has $n+1$ pegs. There are $n$ red pegs arranged as vertices of a regular $n$-sided polygon, numbered from $1$ to $n$ in anti-clockwise order. There is also a blue peg of slightly smaller diameter in the middle of the polygon. A rubber band is stretched around the red pegs.

Doremy is very bored today and has decided to play a game. Initially, she has an empty array $a$. While the rubber band does not touch the blue peg, she will:

1. choose $i$ ($1 \leq i \leq n$) such that the red peg $i$ has not been removed;
2. remove the red peg $i$;
3. append $i$ to the back of $a$.

Doremy wonders how many possible different arrays $a$ can be produced by the following process. Since the answer can be big, you are only required to output it modulo $p$. $p$ is guaranteed to be a prime number.

game with $n=9$ and $a=[7,5,2,8,3,9,4]$ and another game with $n=8$ and $a=[3,4,7,1,8,5,2]$

Doremy 有 $n+1$ 个钉子。其中有 $n$ 个红色钉子，它们构成一个正 $n$ 边形的顶点，按逆时针方向编号为 $1$ 到 $n$。此外，在该正 $n$ 边形的中心还有一个直径略小的蓝色钉子。一根橡皮筋被绷紧在所有红色钉子上。

Doremy 今天非常无聊，决定玩一个游戏。初始时，她有一个空数组 $a$。只要橡皮筋尚未接触到蓝色钉子，她就会重复执行以下操作：

1. 选择一个下标 $i$（$1 \leq i \leq n$），使得红色钉子 $i$ 尚未被移除；
2. 移除红色钉子 $i$；
3. 将 $i$ 追加到数组 $a$ 的末尾。

Doremy 想知道：通过上述过程，一共可能产生多少种不同的数组 $a$？由于答案可能很大，你只需输出其对模数 $p$ 取模的结果。题目保证 $p$ 是一个质数。

左图：$n=9$ 且 $a=[7,5,2,8,3,9,4]$；右图：$n=8$ 且 $a=[3,4,7,1,8,5,2]$

The first line contains two integers $n$ and $p$ ($3 \leq n \leq 5000$, $10^8 \le p \le 10^9$) — the number of red pegs and the modulo respectively.

$p$ is guaranteed to be a prime number.

第一行包含两个整数 $n$ 和 $p$（$3 \leq n \leq 5000$，$10^8 \le p \le 10^9$）—— 分别表示红色钉子的数量和模数。

$p$ 保证为质数。

Output a single integer, the number of different arrays $a$ that can be produced by the process described above modulo $p$.

输出一个整数，表示通过上述过程能够生成的不同数组 $a$ 的数量对 $p$ 取模的结果。

In the first test case, $n=4$, some possible arrays $a$ that can be produced are $[4,2,3]$ and $[1,4]$. However, it is not possible for $a$ to be $[1]$ or $[1,4,3]$.

在第一个测试用例中，$n=4$，一些可能生成的数组 $a$ 包括 $[4,2,3]$ 和 $[1,4]$。然而，$a$ 不可能为 $[1]$ 或 $[1,4,3]$。