N, MOD = map(int, input().split())

def modprd(A_0, A_1):
    a_0, b_0, c_0, d_0 = A_0
    a_1, b_1, c_1, d_1 = A_1
    ret = [0]*4
    ret[0] = (a_0 * a_1 + b_0 * c_1) % MOD
    ret[1] = (a_0 * b_1 + b_0 * d_1) % MOD
    ret[2] = (c_0 * a_1 + d_0 * c_1) % MOD
    ret[3] = (c_0 * b_1 + d_0 * d_1) % MOD
    return ret

def modpow(A, n):
    if n == 0:
        return [1, 0, 0, 1]
    B = modpow(A, n // 2)
    if n & 1:
        return modprd(A, modprd(B, B))
    else:
        return modprd(B, B)

print(modpow([0, 1, 1, 1], N)[0])