FIBOSUM - Fibonacci Sum

no tags 

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

hide comments
karan: 2015-04-22 21:10:20

nice problem ^_^

Prasanna Patil: 2015-04-17 08:41:39

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.

reddragon: 2015-04-03 20:07:19

finally acc

xxbloodysantaxx: 2015-03-17 11:05:35

Try taking out a recurrence for S(n) rather than expressing the sum in fibbonaci term.... Will make you feel better surely :)

Yash: 2015-02-03 20:52:39

My 60th :) Use long datatype...int cost me WAs

abhijeet gusain: 2015-01-29 19:45:53

log(n) + be careful of the negative mod.. :)

AYUSH SAHU: 2015-01-27 17:21:19

finally accepted....:)

Abhinandan Agarwal: 2015-01-24 19:46:50

accepted in 0.00 secs B-)

Anne: 2015-01-24 09:44:03

what do you guys mean by negative modulus?

Raj Kumar Chauhan: 2015-01-22 13:30:07

why WA? :(


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