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
2024-10-14 15:39:05
Good Problem for matrix exponentiation understanding
2024-07-30 14:56:06
Use the property of that The sum of n terms of Fibonacci Sequence is given by Σi=0n Fi = Fn+2 - F2 (or) Fn+2 - 1 as suggested by @prash8830
also take care of negative numbers in modulo operations.
2024-03-10 23:58:06
MY FIRST AC IN ONE!!!!!! LET'S GOOOOOOO!
it's really annoying reading this kind of comments but it doesn't matter if you ac in one or in two or in seven. Just keep coding ;)
2023-03-17 20:18:58
use long long and don't use unsigned long long like me.
make sure you modulus every intermediate matrix sum.
write a helper function for modulus to check if negative and add 1000000007 if so.
fib range sum is fib(M+2) - fib(N+1)

here are some other cases:
1000000 100000000 -> 319410664
10 1000000000 -> 999999926

Last edit: 2023-03-17 20:20:22
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.
2022-01-27 07:12:36
Mod can decrease the value of large interger values
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.
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
2021-02-11 12:48:21
!!IMPORTANT!!
use (a%mod -b%mod +mod)%mod) instead of (a-b)%mod

2020-12-02 15:46:22
Nice problem for matrix exponentiation
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.