피보나치 수 3
시간 제한1초메모리 제한128 MB
n이 10^18까지 커질 수 있는 상황에서 n번째 피보나치 수를 100만으로 나눈 나머지를 행렬 거듭제곱이나 fast doubling으로 구하는 문제입니다.
문제
피보나치 수열은 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으로 나눈 나머지를 출력한다.