分数: 1700 点
问题陈述
对于排列 P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N),定义长度-N 整数序列 f(P) 如下。
-
初始化整数序列 X 与 X=(P_1,P_2,\dots,P_N)。重复以下操作,直至 X 是严格递增的序列。 (可以证明 X 对于任何排列都将是有限次数运算中的严格递增序列 P.)
- 让 k 是最小的索引 i (1 \leq i < N)这样 X_i > X_{i+1}。移动 k- 第一个元素 X 到最后。更准确地说,替换 X 与 (X_1,X_2,\dots,X_{k-1},X_{k+1},X_{k+2},\dots,X_N,X_{k}).
让 C_x 是整数的次数 x 被移动到末尾。然后,定义 f(P)=(C_1,C_2,\dots,C_N).
求一个素数的模数 M,不同的序列可以出现为 f(P).
约束
- 1 \leq N \leq 500
- 10^8 \leq M \leq 10^9
- M 是质数。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M
输出
打印答案。
示例输入 1
4 998244353
示例输出 1
8
例如,当 P=(1,4,3,2),我们初始化 X=(1,4,3,2) 并执行如下操作:
- 自从 X_1 \leq X_2 但是 X_2 > X_3,元素 X_2=4 移至末尾,并且 X 变为 (1,3,2,4).
- X_2=3 移至末尾,并且 X 变为 (1,2,4,3).
- X_3=4 移至末尾,并且 X 变为 (1,2,3,4).
次数 1,2,3,4 移到末尾是 0,0,1,2分别是 f(P)=(0,0,1,2).
示例输入 2
71 998244353
示例输出 2
473972314
示例输入 3
300 923223991
示例输出 3
333532467