Fibonacci Sum

Difficulty: MEDIUM
Avg. time to solve
15 min
Success Rate

Problem Statement
Suggest Edit

Given two integers, ‘N’ and ‘M’, your task is to find the sum of Fibonacci numbers between ‘fib(N)’ and ‘fib(M)’ where ‘fib(N)’ represents the Nth Fibonacci number and ‘fib(M)’ represents the Mth Fibonacci number. The sum is given by sum(N, M) = fib(N) + fib(N+1) + fib(N+2) … fib(M). Since the answer could be large, so you have to return the sum modulo 10^9 + 7.

The fibonacci relation is given by:

fib(0) = 0 
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2), n >= 2, where fib(n) represents the nth fibonacci number.
Input format:
The first line of input contains an integer ‘T’, denoting the number of test cases. 

The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, which denote the start and end of the range.
Output format:
For each test case, print the sum of Fibonacci numbers between ‘fib(N)’ and ‘fib(M)’.

Print the output for each test case in a separate line.
You do not need to print anything. It has already been taken care of. Just implement the given function.
1 <= T <= 1000
0 <= N <= M <= 10^9

Where ‘T’ represents the number of test cases, and ‘N’ and ‘M’ represents the starting and ending of the range respectively.

Time Limit: 1 sec
Sample Input 1:
2 6
0 5
Sample Output 1:
Explanation 1:
For the first test case, 
The Fibonacci numbers between fib(2) and fib(6) are {1, 2, 3, 5, 8}. Their sum is equal to 19. Hence the output is 19.

For the second test case,
The Fibonacci numbers between fib(0) and fib(5) are {0, 1, 1, 2, 3, 5}. Their sum is equal to 12. Hence the output is 12.
Sample Input 2:
3 6
6 7
Sample Output 2:
Reset Code
Full screen