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
2020-09-27 09:36:39
@ks_r 7

Last edit: 2020-09-27 09:40:50
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
2020-07-27 08:52:50
can any one tell what should be ans if i/p is
1
1 1000000000
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.
2020-04-15 07:16:27
How negative values are possible? :).
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
2019-10-26 11:03:38
use (a%mod -b%mod +mod)%mod) instead of (a-b)%mod
2019-09-25 20:42:35
The case of negative modulos is interesting....
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
2019-07-21 21:34:22
Take Care of Data Type...! Got 2 WA for using int and long int.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.