← 返回题目列表

AtCoder · agc035_e

E. 开发

中文机器翻译题面 查看原题

分数: 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