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 \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 翻译