哆瑞咪有 $n+1$ 个钉子。有 $n$ 个红色的钉子排列在一个正 $n$ 边形的顶点上，按逆时针方向从 $1$ 到 $n$ 编号。在多边形的中心还有一个直径略小的蓝色钉子。一根橡皮筋紧紧套在这些红色钉子外侧。

哆瑞咪今天非常无聊，决定玩一个游戏。最开始，她有一个空数组 $a$。只要橡皮筋没有碰到蓝色的钉子，她就会重复以下操作：

1. 选择一个满足红色钉子 $i$ 尚未被移除的 $i$（$1 \le i \le n$）；
2. 移除红色钉子 $i$；
3. 将 $i$ 添加到 $a$ 的末尾。

哆瑞咪想知道通过上述过程可以产生多少种不同的数组 $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 \le n \le 5000$，$10^8 \le p \le 10^9$），分别表示红色钉子的数量和模数。

保证 $p$ 是一个质数。

输出格式

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

样例

输入样例 1

4 100000007

输出样例 1

16

输入样例 2

1145 141919831

输出样例 2

105242108

说明

在第一个样例中，$n = 4$，一些可能产生的数组 $a$ 为 $[4, 2, 3]$ 和 $[1, 4]$。然而，$a$ 不可能是 $[1]$ 或 $[1, 4, 3]$。