题目描述

黒板に $-10^{18}$ から $10^{18}$ までの整数が $1$ 個ずつ書かれています。高橋君は、以下の一連の操作を $0$ 回以上好きなだけ繰り返します。

• 黒板に書かれている整数のうち $1$ 以上 $N$ 以下のものをひとつ選ぶ。選んだ整数を $x$ とし、$x$ を黒板から消す。
• 黒板に $x-2$ が書かれていないなら、$x-2$ を書き加える。
• 黒板に $x+K$ が書かれていないなら、$x+K$ を書き加える。

何回かの操作後、黒板に書かれている数の集合としてありうるものの個数を $M$ で割った余りを求めてください。 ただし、$2$ つの集合が異なるとは、その片方だけに現れるような整数が存在することを指します。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $K$ $M$

输出格式

何回かの操作後、黒板に書かれている数の集合としてありうるものの個数を $M$ で割った余りを出力せよ。

题目大意

在黑板上写有$-10^{18}$到$10^{18}$中的所有整数，每次你可以选中一个$[ 1 , N]$中还在黑板上的整数$x$，把它擦去并补写上$x − 2$ 与 $x + K$（如果原来不存在的话）。你可以进行这个操作任意次（可以不进行），求最终黑板上数字的可能状态有多少种，答案对$M$取模。

$1\leq K \leq N \leq 150 , 10^8\leq M\leq 10^9$

3 1 998244353

7

6 3 998244353

61

9 4 702443618

312

17 7 208992811

128832

123 45 678901234

256109226

提示

制約

• $1\ \leq\ K\leq\ N\ \leq\ 150$
• $10^8\leq\ M\leq\ 10^9$
• $N,K,M$ は整数である

Sample Explanation 1

$0$ 以下または $4$ 以上の整数すべてと、$1,2,3$ のうちの $1$ つ以上を含むような集合すべてが条件を満たし、これは $7$ 通りあります。