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

Output: 0 66616

</p>

Note: If your solution times out, you may try the tutorial version first.