fibo_pisano.py

def fib_mod(num, mod):
    if mod == 1:
        return 0

    seq = [0, 1]
    prev = 0
    curr = 1

    while True:
        prev, curr = curr, (prev + curr) % mod
        seq.append(curr)
        if prev == 0 and curr == 1:
            break

    seq = seq[:-2]

    return seq[num % len(seq)]


def main():
    n, m = map(int, input().split())
    print(fib_mod(n, m))


if __name__ == "__main__":
    main()