/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
英小文字のみからなる文字列 X に対し、以下の手続きによって文字列を得ることを考えます。
- X を異なる文字が隣り合っている部分で分割する。
- 分割した各文字列 Y に対して、Y を Y を構成する文字と Y の長さを繋げた文字列に置き換える。
- 元の順番を保ったまま、置き換えた文字列をすべて繋げる。
例えば、aaabbcccc の場合、aaa,bb,cccc に分けられ、それぞれを a3,b2,c4 に置き換え、その順番のまま繋げることにより a3b2c4 を得ます。また、aaaaaaaaaa の場合、a10 になります。
長さ N の英小文字のみからなる文字列 S のうち、上記の手続きによって得られた文字列 T との長さを比べたとき、T の方が短いものの個数を P で割ったあまりを求めてください。
制約
- 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 で割ったあまりを求めてください。
Score : 500 points
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.