def fast_doubling(n, mod):
    if n == 0:
        return (0, 1)
    a, b = fast_doubling(n >> 1, mod)
    c = (a * ((2 * b - a) % mod)) % mod
    d = (a * a + b * b) % mod
    if n & 1:
        return (d % mod, (c + d) % mod)
    else:
        return (c % mod, d % mod)

n, m = map(int, input().split())
result, _ = fast_doubling(n - 1, m)
print(result % m)