Problem:
 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

Solution (Python):
N, K, M = map(int, input().split())

L = (N+1)//2+1

def even(n, k) :
    
    dp = [[0] * (k+1) for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(n) :
        for j in range(k + 1) :
            dp[i+1][0] = (dp[i+1][0] + dp[i][j]) % M
            
            if j != k :
                dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j]) % M
    
    return sum(dp[n]) % M

def loop(x, y) :
    return (2*x >= K+1 and 2*y >= K+3)
  
if K % 2 == 0 :
    print(even(N//2, K//2) * even((N+1)//2, K//2) % M)
    
else :
    
    
    dp0 = [[[0]*(L+1) for _ in range(L+1)] for _ in range(L+1)]
    dp0[0][0][L] = 1
    
    for i in range(N) :
        dp1 = [[[0]*(L+1) for _ in range(L+1)] for _ in range(L+1)]
        for x in range(L+1) :
            for y in range(L+1) :
                if loop(x, y) : continue
                for z in range(max(x, y)+1, L+1) :
                    if dp0[x][y][z] == 0 :
                        continue
                    dp1[y][x+1][z] += dp0[x][y][z]
                    dp1[y][x+1][z] %= M
                    
                    
                    
                    
                    if y > x :
                        zz = z
                    else :
                        zz = L
                    if 2*y >= K+3 and x > 0 :
                        zz = min(zz, 1+y-x+K//2)
                    dp1[y][0][zz] += dp0[x][y][z]
                    dp1[y][0][zz] %= M
        dp0 = dp1
    
    ret = 0
    for x in range(L+1) :
        for y in range(L+1) :
            if loop(x, y) : continue
            for z in range(max(x, y)+1, L+1) :
                ret += dp0[x][y][z]
                ret %= M
                    
    print(ret)