Easy-Medium

Problem

Editorial

Analytics

Little Shino loves to play with numbers. She just came to know about Fibonacci Series.
Fibonacci Series is a series of number such that

$$Fib(1) = 0$$
$$Fib(2) = 1$$
$$Fib(x) = Fib(x-1) + Fib(x-2)\;where\;2 \lt x$$

Soon Little Shino realized that Fibonacci series grows very fast. So she just wants the sum of last 4 digits of the $$Fib(x)$$ where $$l \le x \le r$$ (mod $$10^9 + 7$$) . Can you help her.

Input:
First line of each test case contains one integer, $$T$$, number of test cases.
Each test case contains two integer, $$l$$ and $$r$$.

Output:
Print the sum of last 4 digits of the $$Fib(x)$$ where $$l \le x \le r$$ (mod $$10^9 + 7$$).

Constraints:
$$1 \le T \le 10^5$$
$$1 \le l \le r \le 10^{18}$$

SAMPLE INPUT

SAMPLE OUTPUT

2
4
68

Explanation

$$Fib(1) = 0$$
$$Fib(2) = 1$$
$$Fib(3) = 1$$
$$Fib(4) = 2$$
$$Fib(8) = 13$$
$$Fib(9) = 21$$
$$Fib(10) = 34$$

First case:
Sum of last 4 digits of $$Fib(1), Fib(2)$$ and $$Fib(3)$$ is 2.

Second case:
Sum of last 4 digits of $$Fib(1), Fib(2), Fib(3)$$ and $$Fib(4)$$ is 4.

Third case:
Sum of last 4 digits of $$Fib(8), Fib(9)$$ and $$Fib(10)$$ is $$(0013 + 0021 + 0034)$$ (mod $$10^9 + 7$$) = $$68$$

Time Limit: 1.0 sec(s) for each input file.

Memory Limit: 256 MB

Source Limit: 1024 KB

Marking Scheme: Marks are awarded when all the testcases pass.

Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...

Contributor

This Problem was Asked in

Challenge Name

July Circuits

All Tracks Math Problem

Easy-Medium

CODE EDITOR

Contributor

This Problem was Asked in

Social Share