피보나치 수의 합

첫 번째 항과 두 번째 항이 모두 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