← 返回题目列表

AtCoder · abc249_e

H. 游程编码

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

分数: 500 点

问题陈述

考虑以下过程,给定一个字符串 X 由小写英文字母组成,获取新字符串:

  • 分割字符串 X 在两个不同字符彼此相邻的位置处关闭。
  • 对于每个字符串 Y 已被拆分,替换 Y 是一个由以下字符组成的字符串 Y 组成,后跟长度 Y.
  • 连接替换的字符串而不改变顺序。

例如, aaabbcccc 分为 aaa,bb,cccc,替换为 a3,b2,c4分别依次连接而不改变顺序,结果是 a3b2c4.如果给定的字符串是 aaaaaaaaaa ,新字符串是 a10 .

求模数 P,字符串 S 长度 N 由小写英文字母组成,这样的长度 T 小于 S,其中 T 是通过上述过程针对字符串得到的字符串 S.

约束

  • 1 \le N \le 3000
  • 10^8 \le P \le 10^9
  • N 和 P 是整数。
  • P 是素数。

输入

输入由标准输入按以下格式给出:

N P

输出

打印答案。


示例输入 1

3 998244353

示例输出 1

26

那些字符串 1-st, 2-nd,和 3-rd字符都相同满足条件。

例如, aaa 变为 a3,满足条件,而 abc 变为 a1b1c1,但没有。


示例输入 2

2 998244353

示例输出 2

0

注意,如果一个字符串转变成另一个相同长度的字符串,比如 aa 变成 a2,不满足条件。


示例输入 3

5 998244353

示例输出 3

2626

字符串如 aaabb 和 aaaaa 满足条件。


示例输入 4

3000 924844033

示例输出 4

607425699

求满足条件模的字符串数量 P.