Score : 1600 points
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:
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.
Input is given from Standard Input in the following format:
N K M
Print the number of possible sets of integers written on the blackboard after some number of operations, modulo M.
3 1 998244353
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.
6 3 998244353
61
9 4 702443618
312
17 7 208992811
128832
123 45 678901234
256109226