SPOJ.com - Problem FIBOSUM

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 <= 10⁹

Submit solution!

hide comments

< Previous 1 2 3 4 5 6 7 8 9 10 11 Next >

	prince_raj123: 2024-10-14 15:39:05 Good Problem for matrix exponentiation understanding
	shailen1003: 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.
	ismaelkno: 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 ;)
	origin_beta: 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
	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.
	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

Submit solution!

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