[AGC035E] Develop

题意翻译

在黑板上写有$-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$

题目描述

[problemUrl]: https://atcoder.jp/contests/agc035/tasks/agc035_e 黒板に $ -10^{18} $ から $ 10^{18} $ までの整数が $ 1 $ 個ずつ書かれています。高橋君は、以下の一連の操作を $ 0 $ 回以上好きなだけ繰り返します。 - 黒板に書かれている整数のうち $ 1 $ 以上 $ N $ 以下のものをひとつ選ぶ。選んだ整数を $ x $ とし、$ x $ を黒板から消す。 - 黒板に $ x-2 $ が書かれていないなら、$ x-2 $ を書き加える。 - 黒板に $ x+K $ が書かれていないなら、$ x+K $ を書き加える。何回かの操作後、黒板に書かれている数の集合としてありうるものの個数を $ M $ で割った余りを求めてください。ただし、$ 2 $ つの集合が異なるとは、その片方だけに現れるような整数が存在することを指します。

输入输出格式

输入格式

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ M $

输出格式

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

输入输出样例

输入样例 #1

3 1 998244353

输出样例 #1

输入样例 #2

6 3 998244353

输出样例 #2

输入样例 #3

9 4 702443618

输出样例 #3

输入样例 #4

17 7 208992811

输出样例 #4

输入样例 #5

123 45 678901234

输出样例 #5

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 $ 通りあります。