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

gnomegeek: 2020-07-22 23:57:40

f(2 * k) = f(k) * f(k) + f(k - 1) * f(k - 1)
f(2 * k + 1) = f(k) * f(k + 1) + f(k - 1) * f(k)
Cant we use these recurrence relations ?
Its O(Log N) time.

pratyushmj1: 2020-04-15 07:16:27

How negative values are possible? :).

surajverma_19: 2020-01-18 07:24:54

Finally AC after 9 WA,3TLE
Done it using matrix exponentiation and modulo
Use modulo in multiplication of each step of matrix

Last edit: 2020-01-18 07:25:25
xom__b: 2019-10-26 11:03:38

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

importme: 2019-09-25 20:42:35

The case of negative modulos is interesting....

violet360: 2019-09-17 18:58:23

normal iteration won't work, will obviously give TLE
use matrix exponentiation(O(log(n))
and use modulo cleverly, good luck :)

Last edit: 2019-09-17 18:59:07
prashantpx_1: 2019-07-21 21:34:22

Take Care of Data Type...! Got 2 WA for using int and long int.


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