EvenOdd

Sum f(X) for every X in [L, R], where f counts the steps of a process that halves even numbers and adds 1 to odd numbers until reaching 1. The bounds reach 10^18.

Hard8MathBit manipulationDivide and conquerDynamic programmingNo attempts yetTime limit2sMemory limit512 MB

Description

Examples2

Problem

Consider the following function $f(X)$ , which takes one positive integer as its argument and returns an integer.

function f(X):
    iterations := 0
    while X is not 1:
        if X is even:
            divide X by 2
        else:
            add 1 to X
        add 1 to iterations
    return iterations

It can be shown that this function terminates for every positive integer $X$ . Given an interval $[L, R]$ , compute the sum

$S = f(L) + f(L + 1) + \cdots + f(R - 1) + f(R)$

Input

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

Output

Print $S$ modulo the prime $10^9 + 7$ .