AT_abc249_e [ABC249E] RLE

题目描述

对于仅由小写英文字母组成的字符串 $X$，我们通过以下过程得到一个新的字符串：

• 在 $X$ 中，每当相邻的字符不同，就将其分割开。
• 对于分割得到的每个字符串 $Y$，将其替换为由 $Y$ 所包含的字符和 $Y$ 的长度拼接而成的新字符串。
• 按照原本的顺序，将所有替换后的字符串拼接起来。

例如，对于 aaabbcccc，可以分割为 aaa、bb、cccc，分别替换为 a3、b2、c4，按顺序拼接得到 a3b2c4。又如，aaaaaaaaaa 会变成 a10。

现在，给定一个长度为 $N$ 的仅由小写英文字母组成的字符串 $S$，请你计算经过上述过程得到的新字符串 $T$ 的长度比 $S$ 短的所有字符串 $S$ 的个数，并对 $P$ 取模后输出。

输入格式

输入通过标准输入给出，格式如下：

$N$ $P$

输出格式

请输出答案。

样例 1

输入

3 998244353

输出

26

样例 2

输入

2 998244353

输出

0

样例 3

输入

5 998244353

输出

2626

样例 4

输入

3000 924844033

输出

607425699

说明/提示

限制条件

• $1 \leq N \leq 3000$
• $10^8 \leq P \leq 10^9$
• $N,P$ 均为整数
• $P$ 是质数

样例解释 1

只有当第 $1,2,3$ 个字符都相同的字符串才满足条件。例如，aaa 会变成 a3，满足条件；但 abc 会变成 a1b1c1，不满足条件。

样例解释 2

注意，像 aa 变成 a2 这样长度相等的情况不满足条件。

样例解释 3

像 aaabb 或 aaaaa 这样的字符串满足条件。

样例解释 4

请输出满足条件的字符串个数对 $P$ 取模的结果。

由 ChatGPT 4.1 翻译