Sum of Tribonacci Numbers

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2793
64-bit integer IO format: %I64d      Java class name: Main

Description

Everybody knows Fibonacci numbers, now we are talking about the Tribonacci numbers:
T[0] = T[1] = T[2] = 1;
T[n] = T[n - 1] + T[n - 2] + T[n - 3] (n >= 3)

Given a and b, you are asked to calculate the sum from the ath Fibonacci number to the bth Fibonacci number, mod 1,000,000,007, that is (T[a] + T[a + 1] + ... + T[b]) % 1,000,000,007.

Input

There are multiple cases (no more than 100).

Each case contain two non-negative integers a b(a <= b and a, b < 1,000,000,000)

Output

For each case, output the sum % 1,000,000,007.

Sample Input

0 2
0 5

Sample Output

3
20

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .