Score : $500$ points

问题描述

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

• 在相邻字符不同的位置将字符串 $X$ 断开。
• 对于每个分割出来的子字符串 $Y$，用由 $Y$ 中包含的字符紧接其后跟上 $Y$ 的长度所组成的新字符串替换 $Y$。
• 不改变顺序地连接所有替换后的字符串。

例如，字符串 aaabbcccc 被分为 aaa、bb 和 cccc，分别被替换为 a3、b2 和 c4，然后不改变顺序地连接起来，得到结果字符串 a3b2c4。如果给定的字符串是 aaaaaaaaaa，则新字符串为 a10。

求满足以下条件的小写英文字母组成长度为 $N$ 的字符串 $S$ 的个数，模 $P$ 后的结果：通过上述过程对字符串 $S$ 进行操作得到的字符串 $T$ 的长度小于 $S$ 的长度。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Consider the following procedure of, given a string $X$ consisting of lowercase English alphabets, obtaining a new string:

• Split the string $X$ off at the positions where two different characters are adjacent to each other.
• For each string $Y$ that has been split off, replace $Y$ with a string consisting of the character which $Y$ consists of, followed by the length of $Y$.
• Concatenate the replaced strings without changing the order.

For example, aaabbcccc is divided into aaa,bb,cccc, which are replaced by a3,b2,c4, respectively, which in turn are concatenated without changing the order, resulting in a3b2c4.If the given string is aaaaaaaaaa , the new string is a10 .

Find the number, modulo $P$, of strings $S$ of lengths $N$ consisting of lowercase English alphabets, such that the length of $T$ is smaller than that of $S$, where $T$ is the string obtained by the procedure above against the string $S$.

Constraints

• $1 \le N \le 3000$
• $10^8 \le P \le 10^9$
• $N$ and $P$ are integers.
• $P$ is a prime.

Input

Input is given from Standard Input in the following format:

$N$ $P$

Output

Print the answer.

Sample Input 1

3 998244353

Sample Output 1

26

Those strings of which the $1$-st, $2$-nd, and $3$-rd characters are all the same satisfy the condition.

For example, aaa becomes a3, which satisfies the condition, while abc becomes a1b1c1, which does not.

Sample Input 2

2 998244353

Sample Output 2

0

Note that if a string is transformed into another string of the same length, such as aa that becomes a2, it does not satisfy the condition.

Sample Input 3

5 998244353

Sample Output 3

2626

Strings like aaabb and aaaaa satisfy the condition.

Sample Input 4

3000 924844033

Sample Output 4

607425699

Find the number of strings satisfying the condition modulo $P$.

update @ 2024/3/10 10:39:08