题目描述

英小文字のみからなる文字列 $X$ に対し、以下の手続きによって文字列を得ることを考えます。

• $X$ を異なる文字が隣り合っている部分で分割する。
• 分割した各文字列 $Y$ に対して、$Y$ を $Y$ を構成する文字と $Y$ の長さを繋げた文字列に置き換える。
• 元の順番を保ったまま、置き換えた文字列をすべて繋げる。

例えば、aaabbcccc の場合、aaa,bb,cccc に分けられ、それぞれを a3,b2,c4 に置き換え、その順番のまま繋げることにより a3b2c4 を得ます。また、aaaaaaaaaa の場合、a10 になります。

長さ $N$ の英小文字のみからなる文字列 $S$ のうち、上記の手続きによって得られた文字列 $T$ との長さを比べたとき、$T$ の方が短いものの個数を $P$ で割ったあまりを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $P$

输出格式

答えを出力せよ。

题目大意

给定一种字符串压缩算法：对于连续的相同字母，会压缩成 该字母 + 出现次数 的形式，例如 aaabbcccc 会被压缩成 a3b2c4，aaaaaaaaaa 会被压缩成 a10。

字符集为英文小写字母，给定 $n, p$，求对于所有长度为 $n$ 的字符串，有多少满足压缩后的字符串长度严格小于原字符串。对 $p$ 取模。保证 $p$ 为质数。

3 998244353

26

2 998244353

0

5 998244353

2626

3000 924844033

607425699

提示

制約

• $1\ \le\ N\ \le\ 3000$
• $10^8\ \le\ P\ \le\ 10^9$
• $N,P$ は整数
• $P$ は素数

Sample Explanation 1

$1,2,3$ 文字目が全て等しい文字列のみが条件を満たします。 例えば、aaa は a3 となり条件を満たしますが、abc は a1b1c1 となり条件を満たしません。

Sample Explanation 2

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

Sample Explanation 3

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

Sample Explanation 4

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