QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100
[+4]

# 6168. 异构序列码性态问题

Statistics

给定四个栈 a,s1,s2,b, 初始时栈 a 包含 n 个元素,从底到顶依次为 1,2,,n, 而 s1,s2,b 均为空

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

  1. a 非空,将 a 栈顶移动到 s1 栈顶;
  2. s1 非空,将 s1 栈顶移动到 s2 栈顶;
  3. s2 非空,将 s2 栈顶移动到 b 栈顶;

但是你有一个额外的要求:任意时刻,s2 从栈顶到栈底的值必须单调递减

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

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

输入格式

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

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

输出格式

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

样例数据

样例输入

4 998244353
5 1000000007
6 1000000009

样例输出

2
30
326

子任务

对于 50% 的数据,N5000

对于 100% 的数据,1N5×105


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