← 返回题目列表

AtCoder · agc071_e

E. 拖延计数器

中文机器翻译题面 查看原题

分数: 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) 并执行如下操作:

  1. 自从 X_1 \leq X_2 但是 X_2 > X_3,元素 X_2=4 移至末尾,并且 X 变为 (1,3,2,4).
  2. X_2=3 移至末尾,并且 X 变为 (1,2,4,3).
  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