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 non-negative 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 non-negative 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 <= 109

Added by:David Gómez
Date:2010-12-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:My Own

hide comments
2015-06-03 13:26:13 Aman Agarwal
AC in one go..
learned a new way to calculate fibonacci series and fibonacci sum
2015-05-21 13:34:16 kartikay singh
NEGATIVE MODULUS COST ME 2WA
FINAlly AC :D
2015-04-22 21:10:20 karan
nice problem ^_^
2015-04-17 08:41:39 Prasanna Patil
When i was using modulo only at answer(final ans) time got TLE.

After that optimized it and used modulo whenever wherever possible. (Got AC in 0.00).
Well learned hell lot of things.
2015-04-03 20:07:19 reddragon
finally acc
2015-03-17 11:05:35 xxbloodysantaxx
Try taking out a recurrence for S(n) rather than expressing the sum in fibbonaci term.... Will make you feel better surely :)
2015-02-03 20:52:39 Yash
My 60th :) Use long datatype...int cost me WAs
2015-01-29 19:45:53 abhijeet gusain
log(n) + be careful of the negative mod.. :)
2015-01-27 17:21:19 AYUSH SAHU
finally accepted....:)
2015-01-24 19:46:50 Abhinandan Agarwal
accepted in 0.00 secs B-)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.