trans_matrix = [[0, 1, 0, 0], [1, 1, 0, 0], [0, 1, 1, 0], [0, 0, 1, 1]]

def matrix_mul(A, B, mod):
    ans = [[0] * len(B[0]) for _ in range(len(A))]
    for i in range(len(A)):
        for j in range(len(B[0])):
            acc_val = 0
            for k in range(len(A[i])):
                acc_val += A[i][k] * B[k][j]

            ans[i][j] = acc_val % mod if mod is not None else acc_val

    return ans

def matrix_pow(A, k, mod):
    if k == 1:
        return A
    if k == 2:
        return matrix_mul(A, A, mod)

    t = matrix_pow(A, k >> 1, mod)
    ans = matrix_mul(A, matrix_mul(t, t, mod), mod) if k % 2 == 1 else matrix_mul(t, t, mod)
    #print(f'k = {k}, ans = {ans}')
    return ans

n, mod = map(int, input().split())
if n == 1:
    print(1)
else:
    trans = matrix_pow(trans_matrix, n-1, mod=mod)
    Sn, Rn = trans[2][0] + trans[2][1] + trans[2][2], trans[3][0] + trans[3][1] + trans[3][2]
    print((n * Sn - Rn) % mod)