def mul_matrix(A, B, M):
    a, b = A[0]
    c, d = A[1]
    e, f = B[0]
    g, h = B[1]
    return [
        [(a*e + b*g) % M, (a*f + b*h) % M],
        [(c*e + d*g) % M, (c*f + d*h) % M],
    ]



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

if N == 1:
    print(0)
    exit()

elif N == 2:
    print(1)
    exit()
    
plus = [
    [1, 1], 
    [1, 0]
]

base = [
    [1, 0], 
    [0, 1]
]

exp = N - 2

while exp > 0:
    if exp & 1:
        base = mul_matrix(base, plus, M)
        
    plus = mul_matrix(plus, plus, M)
    exp >>= 1
    
print(base[0][0])