Bitocja is a developed country with no shortage of experts in mathematics and algorithms. However, in this day and age, that is not enough. The government of Bitocja has decided to start working towards inventing quantum computers that will allow for the efficient solution of even the most difficult problems. The first step in this direction is combining the binary and decimal systems.

The base of the decimal system is 10, and the digits are in the range from 0 to 9. By default, the least significant digit is at the end of the notation, e.g.: $$306 = 6 \cdot 10^0 + 0 \cdot 10^1 + 3 \cdot 10^2 = 6 + 0 + 300$$

The bi-decimal system also uses digits 0-9, but its base is 2. We will denote numbers written in the bi-decimal system with the index "(2;10)", e.g.: $$306_{(2;10)} = 6 \cdot 2^0 + 0 \cdot 2^1 + 3 \cdot 2^2 = 6 + 0 + 12 = 18$$

Thus, the number $306_{(2;10)}$ written in the bi-decimal system represents the number 18 in the decimal system. Technological progress always carries consequences. In this case, it is the lack of uniqueness in the representation of a number.

For a decimal number $x$, let $f(x)$ denote the number of ways to write $x$ in the bi-decimal system. For example, $f(5) = 4$, because there are four representations of the number 5 in this system: $5_{(2;10)}$ $13_{(2;10)}$ $21_{(2;10)}$ $101_{(2;10)}$

Given numbers $L$ and $R$, your task is to calculate the sum $f(L) + f(L + 1) + \dots + f(R)$ and output it modulo $10^9 + 7$.

Input

The only line of input contains two integers $L$ and $R$ ($1 \le L \le R \le 10^{18}$).

Output

The output should contain the number $(f(L) + f(L + 1) + \dots + f(R)) \pmod{10^9 + 7}$.

Examples

Input 1

5 12

Output 1

80

Note

Explanation for the example: $f(5) = 4$ $f(6) = 6$ $f(7) = 6$ $f(8) = 10$ $f(9) = 10$ $f(10) = 13$ $f(11) = 13$ $f(12) = 18$

The sum is $4 + 6 + 6 + 10 + 10 + 13 + 13 + 18 = 80$.