TETRASUM - Sum of Tetranacci numbers (easy)
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 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.
Calculate am + am+1 + ... + an and print the result modulo 1000000007.
Input: 2 1 2 1919 5393 Output: 0 66616
Note: If your solution is fast enough, you may try the classical version.
Similar problems are SEQ and SPP.Last edit: 2015-01-16 21:26:39