피보나치 수의 합
시간 제한2초메모리 제한128 MB
인덱스가 9x10^18까지 가능한 구간에서 피보나치 수의 합을 1e9로 나눈 나머지로 구하며, 행렬 거듭제곱을 이용한 빠른 계산이 필요합니다.
문제
첫 번째 항과 두 번째 항이 모두 1이고, 세 번째 항부터는 바로 앞 두 항의 합으로 정해지는 수열을 피보나치 수열이라고 한다. 따라서 세 번째 항은 2, 네 번째 항은 3이다.
정수 a와 b가 주어졌을 때, 피보나치 수열의 a번째 항부터 b번째 항까지의 합을 구하라. 값이 매우 커질 수 있으므로 합을 1,000,000,000으로 나눈 나머지만 출력한다.
입력
첫째 줄에 두 정수 a와 b가 공백으로 구분되어 주어진다.
출력
첫째 줄에 피보나치 수열의 a번째 항부터 b번째 항까지의 합을 1,000,000,000으로 나눈 나머지를 출력한다.
제약
- 1 <= a <= b <= 9,000,000,000,000,000,000