102494: [AtCoder]ABC249 E - RLE

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$.

问题描述

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

• 在两个不同字符相邻的位置将字符串$X$分割开。
• 对于分割出来的每个字符串$Y$，用一个由$Y$所包含的字符后跟$Y$的长度组成的字符串替换$Y$。
• 按顺序连接替换后的字符串。

例如，aaabbcccc被分为aaa、bb、cccc，分别被替换为a3、b2、c4，进而按顺序连接，得到a3b2c4。如果给定的字符串是aaaaaaaaaa，新字符串是a10。

找出由小写英文字符组成的长度为$N$的字符串$S$的数量（对$P$取模），满足经过上述过程得到的字符串$T$的长度小于$S$的长度。

约束

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

输入

输入从标准输入以以下格式给出：

$N$ $P$

输出

打印答案。

样例输入1

3 998244353

样例输出1

26

那些第1个、第2个和第3个字符都相同的字符串满足条件。

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

样例输入2

2 998244353

样例输出2

0

请注意，如果一个字符串变为另一个长度相同的字符串，如aa变为a2，则不满足条件。

样例输入3

5 998244353

样例输出3

2626

像aaabb和aaaaa这样的字符串满足条件。

样例输入4

3000 924844033

样例输出4

607425699

找出满足条件的字符串的数量（对$P$取模）。