Doremy 的钉子游戏

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

有 $n$ 个红色钉子按逆时针顺序编号为 $1$ 到 $n$，放在正 $n$ 边形的顶点上；正多边形中心还有一个直径略小的蓝色钉子。最初，一根橡皮筋套住所有红色钉子。

Doremy 初始有一个空数组 $a$。只要橡皮筋尚未碰到蓝色钉子，她就重复以下操作：

1. 选择一个尚未移除的红色钉子 $i$；
2. 移除钉子 $i$；
3. 将 $i$ 加到数组 $a$ 的末尾。

求这个过程可能产生多少种不同的数组 $a$。答案对给定质数 $p$ 取模。

输入格式

一行两个整数 $n,p$。$p$ 保证为质数。

输出格式

输出一个整数，表示不同数组的数量对 $p$ 取模的结果。

样例输入 1

4 100000007

样例输出 1

16

样例输入 2

1145 141919831

样例输出 2

105242108

提示

在第一个样例中，$[4,2,3]$ 和 $[1,4]$ 都可能产生，但 $[1]$ 和 $[1,4,3]$ 不可能产生。

数据范围

对所有数据，$3\le n\le5000$，$10^8\le p\le10^9$，且 $p$ 为质数。