题目描述

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

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

输入格式

第一行输入两个整数 $N$ $P$

输出格式

输出一个整数代表答案

3 998244353

26

2 998244353

0

5 998244353

2626

3000 924844033

607425699

样例 1 解释

例如，aaa 变成 a3，满足条件，而 abc 变成 a1b1c1，不满足条件。

提示

• $1 \le N \le 3000$
• $10^8 \le P \le 10^9$
• $N$ 和 $P$ 是整数。
• $P$ 是质数。