题目描述

黑板上写有从 $-10^{18}$ 到 $10^{18}$ 的每一个整数各一个。高桥君可以任意多次（包括 $0$ 次）重复以下操作：

• 从黑板上选择一个 $1$ 到 $N$ 之间的整数，记为 $x$，并将其从黑板上擦去。
• 如果 $x-2$ 不在黑板上，则将 $x-2$ 写到黑板上。
• 如果 $x+K$ 不在黑板上，则将 $x+K$ 写到黑板上。

经过若干次操作后，问黑板上可能出现的整数集合有多少种不同的情况。请输出这个数对 $M$ 取模的结果。
如果存在某个整数只出现在其中一个集合中，则认为两个集合不同。

输入格式

输入为一行，包含三个整数：

$N$ $K$ $M$

输出格式

输出经过若干次操作后，黑板上可能出现的整数集合的种数对 $M$ 取模的结果。

样例 1

输入

3 1 998244353

输出

7

样例 2

输入

6 3 998244353

输出

61

样例 3

输入

9 4 702443618

输出

312

样例 4

输入

17 7 208992811

输出

128832

样例 5

输入

123 45 678901234

输出

256109226

说明/提示

限制条件

• $1 \leq K \leq N \leq 150$
• $10^8 \leq M \leq 10^9$
• $N,K,M$ 均为整数

样例解释 1

所有小于等于 $0$ 或大于等于 $4$ 的整数，以及包含 $1,2,3$ 中至少一个数的所有集合都满足条件，一共有 $7$ 种情况。

由 ChatGPT 4.1 翻译