Doremy 有 $$$n+1$$$ 钉子。有 $$$n$$$ 红色钉子排列为规则 $$$n$$$ 边多边形的顶点,按逆时针顺序编号从 $$$1$$$ 到 $$$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]$$$
输入
第一行包含两个整数 $$$n$$$ 和 $$$p$$$ ($$$3 \leq n \leq 5000$$$, $$$10^8 \le p \le 10^9$$$) — 分别是红色钉子的数量和模数。
$$$p$$$ 保证是素数。
输出
输出单个整数,即通过上述过程对 $$$p$$$ 取模可以生成的不同数组 $$$a$$$ 的数量。
示例
输入 #1
4 100000007
输出 #1
16
输入 #2
1145 141919831
输出 #2
105242108
注意
在第一个测试用例中,$$$n=4$$$,可以生成的一些可能的数组$$$a$$$是$$$[4,2,3]$$$和$$$[1,4]$$$。但是,$$$a$$$ 不可能是$$$[1]$$$ 或$$$[1,4,3]$$$。