FIBOSUM  Fibonacci Sum
The fibonacci sequence is defined by the following relation:
F(0) = 0
F(1) = 1
F(N) = F(N  1) + F(N  2), N >= 2
Your task is very simple. Given two nonnegative integers N and M, you have to calculate the sum (F(N) + F(N + 1) + ... + F(M)) mod 1000000007.
Input
The first line contains an integer T (the number of test cases). Then, T lines follow. Each test case consists of a single line with two nonnegative integers N and M.
Output
For each test case you have to output a single line containing the answer for the task.
Example
Input: 3 0 3 3 5 10 19 Output: 4 10 10857
Constraints
 T <= 1000
 0 <= N <= M <= 10^{9}
hide comments
harsh gupta:
20160611 22:40:31
can anyone post a tricky test case which involves negative modulo ??


lynx_:
20160524 11:50:04
Used Dijkstra's formula...with memorization...


piyushhh:
20160521 16:25:12
I mistakingly printed 1 for 0 0 case . _ . costed me 3 WA!! 

SUBHAM SANGHAI:
20160513 11:02:39
@buttman , Though given n<=m .But you are taking mod with 10^9+7;So there might be a problem of a negative mod.Take this case ,suppose (N!)=(10^9+6) and (M)!=(10^9)+8, (M!)%mod=1 and (N!)%mod=(10^9)+6;


buttman:
20160509 11:18:54
Last edit: 20160514 05:32:30 

harshitdd120:
20160315 18:24:39
Interesting Problem


Vmcode:
20160226 12:45:54
@ abhi_vicky, thanks, got A.C 0.0 

abhi_vicky:
20160224 21:16:50
It is possible in C #Vmcode by using matrix exponantion and sum of fibonacci series!!!!AC in 0.01s 

minhthai:
20160224 13:12:19
that negative modulo tho ( ͡° ͜ʖ ͡°) 

buvaneish:
20160110 16:59:05
i am getting nzec error by pyth 2.7 please help me out it says"maximum recursion depth reached" 
Added by:  David Gómez 
Date:  20101204 
Time limit:  0.838s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  My Own 