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
prash8830: 2022-07-14 08:51:03

Fibonacci Sequence Sum Property :
The sum of n terms of Fibonacci Sequence is given by Σi=0n Fi = Fn+2 - F2 (or) Fn+2 - 1, where Fn is the nth Fibonacci number. (Note: the first term starts from F0)

For example, the sum of first 10 terms of sequence = 12th term - 1 = 89 - 1 = 88. It can be mathematically written as Σi=09 Fi = F11 - 1 = 89 - 1 = 88.

hitesh21: 2022-01-27 07:12:36

Mod can decrease the value of large interger values

ram_321: 2021-12-01 10:06:58

everyone is telling matrix exponentiation but no one is actually explaining the idea behind the summation stuff.
It's not like everyone understands everything, but only some basics like the Fibonacci series or calculating large Fibonacci numbers.

azeez72: 2021-08-24 20:20:38

I like cock

Last edit: 2021-08-25 00:52:28
flashshadow: 2021-05-06 06:49:36

I did matrix exponentiation upto n and then I multiply by matrix power of 2 each time until i reach m, I'm getting the correct answer but time limit is exceeded. Anyone have ideas for removing the stepping by 2 factor? I guess that should be cause. thanks

yash_ver: 2021-02-11 12:48:21

!!IMPORTANT!!
use (a%mod -b%mod +mod)%mod) instead of (a-b)%mod

kokonut_hustle: 2020-12-02 15:46:22

Nice problem for matrix exponentiation

yzs: 2020-09-27 09:36:39

@ks_r 7

Last edit: 2020-09-27 09:40:50
roshan_84ya: 2020-09-21 21:08:28

x1 = ((a[0][0]*b[0][0])%mod + (a[0][1]*b[1][0])%mod)%mod is this is the correct way of modulo in matrix multiplication

ks_r: 2020-07-27 08:52:50

can any one tell what should be ans if i/p is
1
1 1000000000


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