## 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 Arjun Verma: 2015-06-12 15:13:51 1)mod operation on matrix multiplication . 2)take care for mod of a negative number 3)use long long . eagle_19: 2015-06-09 17:23:26 I am getting WA after submitting, but on ideone it's giving the desired output. I've used Matrix method of solving and long int. Surya Sekhar Mondal: 2015-06-06 21:41:31 use long long , cost me 3 WAs priyank: 2015-06-03 13:32:33 use modulus while matrix multiplication and at final answer and take care of neg modulus too :) Aman Agarwal: 2015-06-03 13:26:13 AC in one go.. learned a new way to calculate fibonacci series and fibonacci sum kartikay singh: 2015-05-21 13:34:16 NEGATIVE MODULUS COST ME 2WA FINAlly AC :D karan: 2015-04-22 21:10:20 nice problem ^_^ Prasanna Patil: 2015-04-17 08:41:39 When i was using modulo only at answer(final ans) time got TLE. After that optimized it and used modulo whenever wherever possible. (Got AC in 0.00). Well learned hell lot of things. reddragon: 2015-04-03 20:07:19 finally acc xxbloodysantaxx: 2015-03-17 11:05:35 Try taking out a recurrence for S(n) rather than expressing the sum in fibbonaci term.... Will make you feel better surely :)