SPOJ Problem Set (tutorial) 10724. Sum of Tetranacci numbers (easy) Problem code: TETRASUM

The sequence of Tetranacci numbers is defined as follows:
a_n = a_n-1 + a_n-2 + a_n-3 + a_n-4 with a₀ = a₁ = a₂ = 0 and a₃ = 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 ≤ 10⁹.

Output

Calculate a_m + a_m+1 + ... + a_n and print the result modulo 1000000007.

 

Example

Input:
2
1 2
1919 5393

Output:
0
66616

Note: If your solution is fast enough, you may try the classical version.

---

Added by:	numerix
Date:	2012-02-18
Time limit:	30s
Source limit:	10000B
Languages:	All
Resource:	own problem