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
Arjun Verma: 2015-06-12 15:13:51

1)mod operation on matrix multiplication .
2)take care for mod of a negative number
3)use long long .

eagle_19: 2015-06-09 17:23:26

I am getting WA after submitting, but on ideone it's giving the desired output.
I've used Matrix method of solving and long int.

Surya Sekhar Mondal: 2015-06-06 21:41:31

use long long , cost me 3 WAs

priyank: 2015-06-03 13:32:33

use modulus while matrix multiplication and at final answer and take care of neg modulus too :)

Aman Agarwal: 2015-06-03 13:26:13

AC in one go..
learned a new way to calculate fibonacci series and fibonacci sum

kartikay singh: 2015-05-21 13:34:16

NEGATIVE MODULUS COST ME 2WA
FINAlly AC :D

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


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