[ABC249E] RLE

给定一种字符串压缩算法：对于连续的相同字母，会压缩成 该字母 + 出现次数 的形式，例如 `aaabbcccc` 会被压缩成 `a3b2c4`，`aaaaaaaaaa` 会被压缩成 `a10`。 字符集为英文小写字母，给定 $ n, p $，求对于所有长度为 $ n $ 的字符串，有多少满足压缩后的字符串长度严格小于原字符串。对 $ p $ 取模。保证 $ p $ 为质数。

[problemUrl]: https://atcoder.jp/contests/abc249/tasks/abc249_e 英小文字のみからなる文字列 $ X $ に対し、以下の手続きによって文字列を得ることを考えます。 - $ X $ を異なる文字が隣り合っている部分で分割する。 - 分割した各文字列 $ Y $ に対して、$ Y $ を $ Y $ を構成する文字と $ Y $ の長さを繋げた文字列に置き換える。 - 元の順番を保ったまま、置き換えた文字列をすべて繋げる。 例えば、`aaabbcccc` の場合、`aaa`,`bb`,`cccc` に分けられ、それぞれを `a3`,`b2`,`c4` に置き換え、その順番のまま繋げることにより `a3b2c4` を得ます。また、`aaaaaaaaaa` の場合、`a10` になります。 長さ $ N $ の英小文字のみからなる文字列 $ S $ のうち、上記の手続きによって得られた文字列 $ T $ との長さを比べたとき、$ T $ の方が短いものの個数を $ P $ で割ったあまりを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ 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 $ で割ったあまりを求めてください。