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
priyasatbhaya:
20160909 02:42:29
@baadshah_ thanks for the negative modulus solution 

lakshay_v06:
20160816 22:19:13
In case of a doubt, check out the resources mentioned here : http://programmerheaven9.blogspot.in/2011/10/spojfibosum.html 

swap:
20160731 07:26:43
Learnt a lot! @baadshah_ thanks! It took me some time to understand about negative modulus! 

sonali9696:
20160717 20:48:07
Oh god the mod..! Cost me 9 WAs! You don't have to apply mod to just the answer. You have to apply mod to the matrix at each single step(each time you multiply matrices)!! No idea why even after using long long int!! 

baadshah_:
20160715 20:57:01
if u get negative ans just add 1000000007 to the ans!! 

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 
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 