RLE

题目描述

考虑以下过程：给定一个由小写英文字母组成的字符串 $X$，得到一个新字符串：

在相邻字符不同的位置把字符串 $X$ 切分开。 对于每个被切分出来的字符串 $Y$，用由 $Y$ 所由组成的字符以及 $Y$ 的长度构成的字符串来替换 $Y$。 按原顺序将替换后的字符串连接起来。

例如，$aaabbcccc$ 被分成 $aaa$、$bb$、$cccc$，它们分别被替换为 $a3$、$b2$、$c4$，然后按原顺序连接，得到 $a3b2c4$。如果给定字符串是 $aaaaaaaaaa$，新字符串是 $a10$。 求满足以下条件的长度为 $N$ 的由小写英文字母组成的字符串 $S$ 的数量（模 $P$），其中对于字符串 $S$，用上述过程得到的字符串记为 $T$，并且要求 $T$ 的长度小于 $S$ 的长度。

输入格式

从标准输入给出输入，格式如下： $N$ $P$

输出格式

输出答案。

3 998244353

26

2 998244353

0

5 998244353

2626

3000 924844033

607425699

提示

$1 \le N \le 3000$ $10^8 \le P \le 10^9$ $N$ 和 $P$ 是整数。 $P$ 是素数。当字符串的第 1、2、3 个字符都相同时，它们满足条件。 例如，$aaa$ 会变成 $a3$，满足条件，而 $abc$ 会变成 $a1b1c1$，不满足条件。
注意如果一个字符串被变换为相同长度的字符串，例如 $aa$ 变成 $a2$，则不满足条件。
像 $aaabb$ 和 $aaaaa$ 这样的字符串满足条件。
求满足条件的字符串数量模 $P$。

标签: AtCoder|abc249E

来源

AtCoder|abc249E