spoj#TETRAHRD. Sum of Tetranacci numbers
Sum of Tetranacci numbers
The sequence of Tetranacci numbers is defined as follows:
an = an-1 + an-2 + an-3 + an-4 with a0 = a1 = a2 = 0 and a3 = 1.
Input
Input starts with a positive integer t ≤ 4000, then t lines follow. Each of the t lines contains two space separated integers m and n with 0 ≤ m ≤ n ≤ 109.
Output
Calculate am + am+1 + ... + an and print the result modulo 1000000007.
Example
Input: 2 1 2 1919 5393</p>Output: 0 66616
Note: If your solution times out, you may try the tutorial version first.