smoothie-web Problems Contests Ranking About

# BSSPC '20 J5

James remember his days when he had just learned the fibonacci sequence. To refresh your memory, the fibonacci sequence is defined as:

$fib(1) = 1, fib(2) = 1, fib(x) = fib(x-1) + fib(x-2), \text { for } x \ge 3$

Since he loves giving other coders challenge, he has given one to you! You challenge is to answer $Q$ of James's questions, each question is asking you for the sum of all the fibonacci numbers in the range $[l, r]$ inclusive. Or written in sum notation is:

$\sum_{x=l}^{r} fib(x)$

Since this number is quite big, output the answer$\mod 10^9 + 7$.

The $\bmod$ operator is built into all programming languages. It returns values such that $a \bmod b$ returns the remainder left over after $a$ is divided by $b$.

## Input Specification

The first line of input contains $Q$, the number of questions James is going to ask you.

The next $Q$ lines will contain two integers, $l, r$, denoting the range of the summation.

## Output Specification

For each question, output the sum.

## Constraints

For all subtasks:

$1 \le Q \le 10^6$

$1 \le l \le r \le 10^6$

### Subtask 1 [25%]

$1 \le Q \le 100$

$1 \le l \le r \le 20$

### Subtask 2 [25%]

$1 \le Q \le 10^4$

$r - l \le 100$

### Subtask 3 [50%]

No further constraints.

### Sample Input

2
1 3
2 4


### Sample Output

4
6


### Sample Explantion

The first four fibonacci numbers are $\{ 1, 1, 2, 3 \}$.

For the first query, the sum of the first three fibonaaci numbers are $1 + 1+ 2 = 4$.

Similarly, the sum of the fiboannci numbers in the range $[2, 4]$ is $1 + 2 + 3 = 6$