## 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 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 :) Yash: 2015-02-03 20:52:39 My 60th :) Use long datatype...int cost me WAs abhijeet gusain: 2015-01-29 19:45:53 log(n) + be careful of the negative mod.. :) AYUSH SAHU: 2015-01-27 17:21:19 finally accepted....:) Abhinandan Agarwal: 2015-01-24 19:46:50 accepted in 0.00 secs B-) Anne: 2015-01-24 09:44:03 what do you guys mean by negative modulus? Raj Kumar Chauhan: 2015-01-22 13:30:07 why WA? :(