分数: 1600 点
问题陈述
有一块黑板,上面所有的整数 写有 -10^{18} 通过 10^{18} ,每个都出现一次。高桥将重复以下操作序列任意次数,可能为零:
- 选择一个整数 黑板上写着 1 和 N (含)。让 x 为所选整数,并擦除 黑板上没有写 x.
- If x-2 ,写 x-2 。
- If x+K ,写 x+K 。
经过一定次数的运算后求出黑板上写的可能的整数组的数量,取模 M。 当存在仅包含在其中一个集合中的整数时,我们认为两个集合不同。
约束
- 1 \leq K\leq N \leq 150
- 10^8\leq M\leq 10^9
- N, K,和 M 是整数。
输入
输入由标准输入按以下格式给出:
N K M
输出
打印经过一定次数的运算后写在黑板上的可能的整数组的数量,取模 M.
样本输入 1
3 1 998244353
示例输出 1
7
包含所有小于的整数的每个集合 1,所有大于的整数 3,以及三个整数中的至少一个 1, 2,和 3 满足条件。这样的集合有七组。
示例输入 2
6 3 998244353
示例输出 2
61
示例输入 3
9 4 702443618
示例输出 3
312
示例输入 4
17 7 208992811
示例输出 4
128832
示例输入 5
123 45 678901234
示例输出 5
256109226