[백준, 2749번] 피보나치 수 3

# 피사노 주기라는 것을 활용해서 푼 풀이
# 우선 문제에서 1,000,000으로 나눈 나머지의 값을 제출해라고 했기에
# 이때 나누는 값이 100보다 크다면 
# 반복되는 주기는 나누려고 하는 나머지의 값인 15*10**(6-1) 라고 한다
# 10**(6)은 기존 1,000,000를 의미하고 여기서 15와 10**(6-1)를 해준 값이 주기가 된다.
# 그래서 for문에는 n 값에 15와 10**(6-1)인 p값으로 나눈 나머지 횟수만 반복하게 하기.
# 또한 a와 b 값은 1,000,000로 나눈 나머지 값을 가지게 하기
a,b = 0,1
m, p = 1000000, 1500000
for _ in range((int(input())+1)%p):
    a, b = (a+b)%m, a%m
print(b)