TETRAHRD  Sum of Tetranacci numbers
The sequence of Tetranacci numbers is defined as follows:
a_{n} = a_{n1} + a_{n2} + a_{n3} + a_{n4} 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 times out, you may try the tutorial version first.
hide comments
matinzare:
20210412 17:53:21
with the correct solution time limit is enough 

amulyagaur:
20170830 22:08:24
Needs a lot of optimisations :) ... ac after many tle's 

sxie12:
20170718 00:56:23
Very strict time limit. Had to remove unnecessary mod operations to AC. TLE otherwise. 

Sarthak Taneja:
20150810 16:58:22
Getting tle any suggestions?? 

Subrat Singh:
20150418 22:05:01
Last edit: 20160114 06:33:59 

Francky:
20130102 11:43:00
It was really very hard to get AC with my order_4 python3 solution, but now we can say it's possible !

Added by:  numerix 
Date:  20120226 
Time limit:  1s 
Source limit:  10000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  own problem 