给定四个栈 $a, s_1, s_2, b$, 初始时栈 $a$ 包含 $n$ 个元素，从底到顶依次为 $1,2,\cdots,n$, 而 $s_1,s_2,b$ 均为空

你可以进行若干次以下操作：

1. 若 $a$ 非空，将 $a$ 栈顶移动到 $s_1$ 栈顶；
2. 若 $s_1$ 非空，将 $s_1$ 栈顶移动到 $s_2$ 栈顶；
3. 若 $s_2$ 非空，将 $s_2$ 栈顶移动到 $b$ 栈顶；

但是你有一个额外的要求：任意时刻，$s_2$ 从栈顶到栈底的值必须单调递减

最终，所有元素均在 $b$ 中，把它当作序列从顶到底写出来。

异构序列码性态问题：求有多少个排列不能得到，对质数 $M$ 取模。

输入格式

每个测试点中包含多组测试数据。

输入的第一行包含两个整数 $N, M$。

输出格式

对于每组测试数据，输出一行一个整数，表示答案。

样例数据

样例输入

4 998244353
5 1000000007
6 1000000009

样例输出

2
30
326

子任务

对于 $50\%$ 的数据，$N \leq 5\,000$。

对于 $100\%$ 的数据，$1 \leq N \leq 5 \times 10^5$。

注

1. 赛时并未提供数据组数，“请选手自行评估”。
2. 赛时并未提供模数 $M$ 的范围，“请选手自行评估”。
3. 赛时并未提供空间限制，“请选手自行评估” QOJ 上设置为 1 GB。