RLE 压缩

题目描述

考虑对由小写英文字母组成的字符串 $X$,通过以下过程得到一个新字符串:

• 在相邻字符互不相同的所有位置处将字符串 $X$ 切分。
• 对每个切分得到的字符串 $Y$,将其替换为由「$Y$ 所包含的字符」和「$Y$ 的长度」组成的字符串。
• 保持顺序不变,将替换后的字符串拼接起来。

例如,aaabbcccc 被切分为 aaa、bb、cccc,分别替换为 a3、b2、c4,再保持顺序不变地拼接,得到 a3b2c4。若给定字符串是 aaaaaaaaaa,则新字符串是 a10。

求:由小写英文字母组成的长度为 $N$ 的字符串 $S$ 中,满足「按上述过程得到的字符串 $T$ 的长度小于 $S$ 的长度」的字符串 $S$ 的个数,对 $P$ 取模。

输入格式

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

N P

输出格式

输出答案。

样例

3 998244353

26

所有第 $1$、$2$、$3$ 个字符都相同的字符串满足条件。

例如,aaa 变为 a3,满足条件;而 abc 变为 a1b1c1,不满足条件。

2 998244353

0

注意:若变换后得到的字符串与原字符串长度相同,如 aa 变为 a2,则不算满足条件。

5 998244353

2626

aaabb、aaaaa 等字符串满足条件。

3000 924844033

607425699

求满足条件的字符串个数对 $P$ 取模后的值。

数据范围

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