← 返回题目列表

Codeforces · 1764/D

D. 多米的挂钩游戏

中文机器翻译题面 查看原题

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]$$$。