TETRAHRD - Sum of Tetranacci numbers

no tags 

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

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


hide comments
matinzare: 2021-04-12 17:53:21

with the correct solution time limit is enough

amulyagaur: 2017-08-30 22:08:24

Needs a lot of optimisations :) ... ac after many tle's

sxie12: 2017-07-18 00:56:23

Very strict time limit. Had to remove unnecessary mod operations to AC. TLE otherwise.

Sarthak Taneja: 2015-08-10 16:58:22

Getting tle any suggestions??

Francky: 2013-01-02 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 !
Edit : Python2 is still possible too without psyco.

Last edit: 2013-01-02 20:36:24

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