smoothie-web Problems Contests Ranking About
Login Register

J5 - Playing With Fibonacci

data_usage Points
timer Time Limit
linear_scale Memory Limit

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(x1)+fib(x2), for x3fib(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 QQ of James's questions, each question is asking you for the sum of all the fibonacci numbers in the range [l,r][l, r] inclusive. Or written in sum notation is:

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

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

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

Input Specification

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

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

Output Specification

For each question, output the sum.


For all subtasks:

1Q1061 \le Q \le 10^6

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

Subtask 1 [25%]

1Q1001 \le Q \le 100

1lr201 \le l \le r \le 20

Subtask 2 [25%]

1Q104 1 \le Q \le 10^4

rl100r - l \le 100

Subtask 3 [50%]

No further constraints.

Sample Input

1 3
2 4

Sample Output


Sample Explantion

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

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

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

Problem Credits


James Su


James Su, Lakshy Gupta