피보나치 수 3

피보나치 수열은 0과 1에서 시작한다. 0번째 피보나치 수는 0, 1번째 피보나치 수는 1이다. 2번째부터는 바로 앞의 두 피보나치 수를 더한 값이다.

n ≥ 2에 대해 F_n = F_{n-1} + F_{n-2}로 나타낼 수 있다.

n=17까지의 피보나치 수는 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어질 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

첫째 줄에 자연수 n이 주어진다. n은 1,000,000,000,000,000,000 이하이다.

첫째 줄에 n번째 피보나치 수를 1,000,000으로 나눈 나머지를 출력한다.