分数: 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.