/ 
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 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 で割った余りを出力せよ。
入力例 1
3 1 998244353
出力例 1
7
0 以下または 4 以上の整数すべてと、1,2,3 のうちの 1 つ以上を含むような集合すべてが条件を満たし、これは 7 通りあります。
入力例 2
6 3 998244353
出力例 2
61
入力例 3
9 4 702443618
出力例 3
312
入力例 4
17 7 208992811
出力例 4
128832
入力例 5
123 45 678901234
出力例 5
256109226
Score : 1600 points
Problem Statement
There is a blackboard on which all integers from -10^{18} through 10^{18} are written, each of them appearing once. Takahashi will repeat the following sequence of operations any number of times he likes, possibly zero:
- Choose an integer between 1 and N (inclusive) that is written on the blackboard. Let x be the chosen integer, and erase x.
- If x-2 is not written on the blackboard, write x-2 on the blackboard.
- If x+K is not written on the blackboard, write x+K on the blackboard.
Find the number of possible sets of integers written on the blackboard after some number of operations, modulo M. We consider two sets different when there exists an integer contained in only one of the sets.
Constraints
- 1 \leq K\leq N \leq 150
- 10^8\leq M\leq 10^9
- N, K, and M are integers.
Input
Input is given from Standard Input in the following format:
N K M
Output
Print the number of possible sets of integers written on the blackboard after some number of operations, modulo M.
Sample Input 1
3 1 998244353
Sample Output 1
7
Every set containing all integers less than 1, all integers greater than 3, and at least one of the three integers 1, 2, and 3 satisfies the condition. There are seven such sets.
Sample Input 2
6 3 998244353
Sample Output 2
61
Sample Input 3
9 4 702443618
Sample Output 3
312
Sample Input 4
17 7 208992811
Sample Output 4
128832
Sample Input 5
123 45 678901234
Sample Output 5
256109226