每个人都在快乐地编码,直到突然发生电力短缺,最好的竞争性编程网站瘫痪了。幸运的是,一位系统管理员最近购买了一些新设备,其中包括一些UPS。因此,有一些服务器仍然在线,但我们需要所有服务器都正常工作才能保持回合评级。
想象服务器是一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$。如果第 $$$i$$$ 服务器在线,则 $$$s_i = 1$$$,否则 $$$s_i = 0$$$。
系统管理员可以执行以下称为电力传播的操作,该操作包括以下阶段:
- 选择位置 $$$1 \le i < j \le n$$$ 的两台服务器,使两者都在线(即 $$$s_i=s_j=1$$$)。传播仅从在线服务器开始。
- 检查我们是否有足够的力量来进行传播。如果 $$$[i, j]$$$ 范围内打开的服务器数量至少等于 $$$[i, j]$$$ 范围内关闭的服务器数量,我们就认为拥有足够的电量。更正式地说,检查是否 $$$2 \cdot (s_i + s_{i+1} + \ldots + s_j) \ge j - i + 1$$$。
- 如果检查结果为肯定,则打开 $$$[i, j]$$$ 范围内的所有离线服务器。更正式地说,对于从 $$$i$$$ 到 $$$j$$$ 的所有 $$$k$$$,使 $$$s_k := 1$$$ 成立。
如果我们可以使用电力传播操作任意次数(可能是 $$$0$$$)打开所有服务器(即,使 $$$s_i = 1$$$ for $$$1 \le i \le n$$$),那么我们将长度为 $$$n$$$ 的二进制字符串 $$$s$$$ 称为额定值。您的任务是找到长度为 $$$n$$$ 以 $$$m$$$ 为模的额定字符串的数量。
输入
第一行也是唯一一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 5000$$$, $$$10 \le m \le 10^9$$$) — 字符串的长度和所需的模块。
输出
打印单个整数 — 长度为 $$$n$$$ 的额定二进制字符串的数量。由于这个数字可能很大,因此打印它对 $$$m$$$ 取模。
示例
输入 #1
2 100
输出 #1
1
输入 #2
3 10
输出 #2
2
输入 #3
4 3271890
输出 #3
4
输入#4
17 123456
输出#4
32347
注意
在第一个示例中,唯一评级的字符串是 11。因此答案是 $$$1$$$。
在第二个示例中,额定字符串为:
- 111;
- 101,因为我们可以执行 $$$i = 1$$$ 和 $$$j = 3$$$ 的操作。
在第三个示例中,额定字符串为:
- 1001;
- 1111;
- 1011;
- 1101.