题目描述

汪老师有 $n+1$ 个钉子，它将它们钉在一个平面上。

其中有 $n$ 个红色的钉子，以这 $n$ 个钉子作为顶点能够形成一个正 $n$ 边形。这 $n$ 个钉子按逆时针从 $1$ 编号到 $n$。

还有一个蓝色的钉子，这个钉子比其它钉子的直径要稍微小一点点，它坐落在正 $n$ 边形的中心。

初始的时候还有一根橡皮筋，它缠绕在红色的钉子外面。

汪老师今天非常无聊所以他准备玩一个游戏。初始时，他有一个空的数列 $a$。只要橡皮筋没有碰到蓝色的钉子，它就会一直执行如下操作：

1. 选择编号为 $i(1 \le i \le n)$ 的红色钉子 —— 要求是这个钉子目前没有被移除；
2. 移除掉编号为 $i$ 的红色钉子；
3. 将 $i$ 添加到数列 $a$ 的末尾。

汪老师想要知道最终的数列 $a$（即：进行最后一次操作后橡皮筋碰到蓝色钉子对应的数列 $a$）有多少种不同的可能。

由于方案数可能很多，所以你只需要输出总的方案数模 $p$ 的结果即可。

上图演示了 $n=9$ 且 $a=[7,5,2,8,3,9,4]$ 以及 $n = 8$ 且 $a=[3,4,7,1,8,5,2]$ 时的两个例子。

注：如果你是pdf文件，或者没有看到上方的动画，你可以点击 此链接 查看上方动画

输入格式

一行，两个整数 $n$ 和 $p$（$3 \le n \le 5000, 10^8 \le p \le 10^9$）——分别表示红色钉子的数量以及要模的那个数字。

数据保证 $p$ 是一个素数。

输出格式

输出一个整数，表示最终得到的不同数列 $a$ 的数量模 $p$ 的结果。

样例输入1

4 100000007

样例输出1

16

样例输入2

1145 141919831

样例输出2

105242108

说明/提示

样例 1 解释

样例1中，最终的排列 $a$ 一共有 $16$ 种情况，它们分别是：

• $1,2$
• $1,3,2$
• $1,3,4$
• $1,4$
• $2,1$
• $2,3$
• $2,4,1$
• $2,4,3$
• $3,1,2$
• $3,1,4$
• $3,2$
• $3,4$
• $4,1$
• $4,2,1$
• $4,2,3$
• $4,3$

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 10$
• 对于 $60\%$ 的数据，$n \le 500$
• 对于 $100\%$ 的数据，$3 \le n \le 5000, 10^8 \le p \le 10^9$