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

Code Examples

#1 Code Example with Python Programming

```Code - Python Programming```

``````class matrix:
a = []

def __init__(self, default=None):
if default is not None:
self.a = default
else:
self.a = [[0, 0], [0, 0]]

def __mul__(self, other):
s = matrix()
for i in range(2):
for j in range(2):
for k in range(2):
s.a[i][j] += self.a[i][k] * other.a[k][j]
for i in range(2):
for j in range(2):
s.a[i][j] %= 1000000007
return s

def __pow__(self, power, modulo=None):
if power == 1:
return matrix([[1, 1], [1, 0]])
if power % 2 == 1:
return self * (self.__pow__(power - 1))
half = self.__pow__(power // 2)
return half * half

def get(n, modulo):
m = matrix([[1, 1], [1, 0]]) ** (n + 2)
return (m.a[0][1] + modulo - 1) % modulo

modulo = 1000000007
T = int(input())
for _ in range(T):
N, M = map(int, input().split())
print((get(M, modulo) - get(N - 1, modulo) + modulo) % modulo)``````
Copy The Code &

Input

cmd
3
0 3
3 5
10 19

Output

cmd
4
10
10857