Sum of Fibonacci Numbers

The Fibonacci sequence is defined by F_1 = 1 and F_2 = 1. For n >= 3, F_n is the sum of the previous two terms. Therefore F_3 = 2 and F_4 = 3.

Given integers a and b, compute F_a + F_(a+1) + ... + F_b. Since the sum can be very large, output only its remainder modulo 1,000,000,000.

The first line contains two integers a and b separated by a space.

Print the requested sum modulo 1,000,000,000 on the first line.

• 1 <= a <= b <= 9,000,000,000,000,000,000