# 피사노 주기라는 것을 활용해서 푼 풀이 # 우선 문제에서 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)
