当前没有测试数据。

E - RLE

得分: $500$ 分

问题描述

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

• 在两个不同字符相邻的位置处分割字符串 $X$。
• 对于每个被分割下来的字符串 $Y$，用由 $Y$ 组成的字符和 $Y$ 的长度替换 $Y$。
• 按原有的顺序连接替换后的字符串。

例如，aaabbcccc 被分割成 aaa，bb，cccc，它们分别被替换为 a3，b2，c4，然后按照原有的顺序连接，得到 a3b2c4。如果给定的字符串是 aaaaaaaaaa，则新的字符串是 a10。

求长度为 $N$，由小写英文字母组成的字符串 $S$ 的数量（对 $P$ 取模），满足 $T$ 的长度小于 $S$ 的长度，其中 $T$ 是对 $S$ 使用上述过程而得到的字符串。

约束

• $1 \le N \le 3000$
• $10^8 \le P \le 10^9$
• $N$ 和 $P$ 是整数。
• $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$ 取模。