配点 : $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$

出力

答えを出力せよ。

3 998244353

26

$1,2,3$ 文字目が全て等しい文字列のみが条件を満たします。

例えば、aaa は a3 となり条件を満たしますが、abc は a1b1c1 となり条件を満たしません。

2 998244353

0

aa → a2 のように、長さが等しいものは条件を満たさないことに注意してください。

5 998244353

2626

aaabb や aaaaa などが条件を満たします。

3000 924844033

607425699

条件を満たす文字列の個数を $P$ で割ったあまりを求めてください。