TETRASUM - Sum of Tetranacci numbers (easy)
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_{0} = a_{1} = a_{2} = 0 and a_{3} = 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^{9}.
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.
hide comments
numerix:
2012-03-13 14:03:41
Similar problems are SEQ and SPP. Last edit: 2015-01-16 21:26:39 |
Added by: | numerix |
Date: | 2012-02-18 |
Time limit: | 5s |
Source limit: | 10000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | own problem |