配点 : $1600$ 点

問題文

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

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

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

制約

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

入力

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

$N$ $K$ $M$

出力

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

3 1 998244353

7

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

6 3 998244353

61

9 4 702443618

312

17 7 208992811

128832

123 45 678901234

256109226