## Fibonacci Calculation

View as PDF

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
C, C++, Java, Python

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 specification

The first line contains an integer $$T <= 1000$$ (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, $$0 \leq N \leq M \leq 10^9$$.

#### Output specification

For each test case you have to output a single line containing the answer for the task.

#### Sample input

3
0 3
3 5
10 19

#### Sample output

4
10
10857