백준 알고리즘 2749번 피보나치 수 3(python)

이 문제는 피사노 주기를 알면 쉽게 풀 수 있다. 피보나치 수를 나눈 수는 항상 주기를 가지는데,

피보나치 수를 나눌 수를 k라고 할 때, k = 10^n이면 피사노 주기는 15 * 10^(n-1)이다.

n = int(input())
a, b = 0, 1
n = n % (15*100000)
for i in range(n):
    a, b = b%1000000, (a+b)%1000000
print(a)