Contest Duration: - (local time) (130 minutes) Back to Home
E - Develop /

Time Limit: 5 sec / Memory Limit: 1024 MB

問題文

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

制約

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

入力

N K 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