给定四个栈 a,s1,s2,b, 初始时栈 a 包含 n 个元素,从底到顶依次为 1,2,⋯,n, 而 s1,s2,b 均为空
你可以进行若干次以下操作:
- 若 a 非空,将 a 栈顶移动到 s1 栈顶;
- 若 s1 非空,将 s1 栈顶移动到 s2 栈顶;
- 若 s2 非空,将 s2 栈顶移动到 b 栈顶;
但是你有一个额外的要求:任意时刻,s2 从栈顶到栈底的值必须单调递减
最终,所有元素均在 b 中,把它当作序列从顶到底写出来。
异构序列码性态问题:求有多少个排列不能得到,对质数 M 取模。
输入格式
每个测试点中包含多组测试数据。
输入的第一行包含两个整数 N,M。
输出格式
对于每组测试数据,输出一行一个整数,表示答案。
样例数据
样例输入
4 998244353
5 1000000007
6 1000000009
样例输出
2
30
326
子任务
对于 50% 的数据,N≤5000。
对于 100% 的数据,1≤N≤5×105。
注
- 赛时并未提供数据组数,“请选手自行评估”。
- 赛时并未提供模数 M 的范围,“请选手自行评估”。
- 赛时并未提供空间限制,
“请选手自行评估”QOJ 上设置为 1 GB。