AT_agc035_e [AGC035E] Develop

黑板上写有从 $-10^{18}$ 到 $10^{18}$ 的每一个整数各一个。高桥君可以任意多次（包括 $0$ 次）重复以下操作： - 从黑板上选择一个 $1$ 到 $N$ 之间的整数，记为 $x$，并将其从黑板上擦去。 - 如果 $x-2$ 不在黑板上，则将 $x-2$ 写到黑板上。 - 如果 $x+K$ 不在黑板上，则将 $x+K$ 写到黑板上。 经过若干次操作后，问黑板上可能出现的整数集合有多少种不同的情况。请输出这个数对 $M$ 取模的结果。 如果存在某个整数只出现在其中一个集合中，则认为两个集合不同。

输入为一行，包含三个整数： > $N$ $K$ $M$

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

### 限制条件 - $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 翻译