Fibonacci problem again#1250
Sign in

Fibonacci problem again

1 second
128 megabytes
Medium

As is well known, the Fibonacci numbers are defined as follows:

F(n) = \begin{cases} 0, & n = 0, \\ 1, & n = 1, \\ F(n - 1) + F(n - 2), & n > 1. \end{cases}

Given two integers and , compute the sum:

S = F(a) + F(a+1) + \ldots + F(b)

Input

Each line represents a separate test case and contains two integers and b~(0 \le a \le b \le 10^9).

Output

For each test case, print on a separate line the value of modulo 10^9 + 7.

Examples

Example 1

Loading
Loading