6659: ABC249 — E - RLE
[Creator : ]
Description
Consider the following procedure of, given a string $X$ consisting of lowercase English alphabets, obtaining a new string:
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$.
- 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.
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$.
Input
Input is given from Standard Input in the following format:
$N\ P$
$N\ P$
Output
Print the answer.
Constraints
$1≤N≤3000$
$10^8 \le P \le 10^9$
$N$ and $P$ are integers.
$P$ is a prime.
$10^8 \le P \le 10^9$
$N$ and $P$ are integers.
$P$ is a prime.
Sample 1 Input
3 998244353
Sample 1 Output
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.
For example, aaa becomes a3, which satisfies the condition, while abc becomes a1b1c1, which does not.
Sample 2 Input
2 998244353
Sample 2 Output
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 3 Input
5 998244353
Sample 3 Output
2626
Strings like aaabb and aaaaa satisfy the condition.
3000 924844033
607425699