## 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

 < Previous 1 2 3 4 5 6 7 8 9 10 11 Next > 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*b)%mod + (a*b)%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