fibonacci_huge

# Uses python3
import sys


def get_fibonacci_huge_naive(n, m):
    if n <= 1:
        return n

    previous = 0
    current = 1

    for _ in range(n - 1):
        previous, current = current, previous + current

    return current % m


#  property of the Fibonacci remainders of modulo n operation is that you can find the next remainder by adding
#  the last 2 and looped on n ie. for F(13) mod 5 , r(13) = r(11) + r(12) = 4 + 4 =  3 because 8 = 5 + 3
#  also the pattern of remainders repeat every time you encounter the a 0 followed by a 1. That is the mark for the
#  length of the Pisano period.


def get_fibonacci_huge_faster(p, q):
    if p <= 1:
        return p

    previous = 1
    current = 1
    pisanoPeriod = 1

    while (previous, current) != (0, 1):
        #  we loop back on q to get the remainder of the remainders sum
        previous, current = current, (previous + current) % q
        pisanoPeriod += 1
    #  we just need to find the remainder of p when divided by the Pisano period.
    #  numbers are small enough now to use the naive approach
    return get_fibonacci_huge_naive(p % pisanoPeriod, q)


if __name__ == '__main__':
    user_input = sys.stdin.read()
    a, b = map(int, user_input.split())
    # print(get_fibonacci_huge_naive(a, b))
    print(get_fibonacci_huge_faster(a, b))