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
anurag_tangri: 2017-04-05 16:02:14

2 TLE 2 WA and finally AC:)

rv404674: 2017-03-27 15:51:21

ac in 0.00 using fast matrix exponentiation

vineetpratik: 2017-03-14 07:43:06

Dijkstra's fibonacci formula- 0.09sec 92M
Fast Matrix Exponentiation - 0.01sec 16M

vineetpratik: 2017-03-10 17:35:55

Dijkstra's fibonacci formula

nilabja16180: 2017-03-04 09:09:01

Use long long, costed me one WA!

priyasatbhaya: 2016-09-09 02:42:29

@baadshah_ thanks for the negative modulus solution

lakshay_v06: 2016-08-16 22:19:13

In case of a doubt, check out the resources mentioned here : http://programmerheaven9.blogspot.in/2011/10/spoj-fibosum.html

swap: 2016-07-31 07:26:43

Learnt a lot! @baadshah_ thanks! It took me some time to understand about negative modulus!

sonali9696: 2016-07-17 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_: 2016-07-15 20:57:01

if u get negative ans just add 1000000007 to the ans!!


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