import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

def F(n):
    if n == 0:
        return 1,0
    a,b = F(n//2)
    a,b = a*a + b*b, 2*a*b + b*b
    a %= MOD
    b %= MOD
    if n&1:
        return b,a+b
    else:
        return a,b

answer = F(N)[0] % MOD

print(answer)