KTH Challenge 2017 Open Online Contest

Start

2017-06-11 10:00 CEST

KTH Challenge 2017 Open Online Contest

End

2017-06-11 14:00 CEST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -166 days 21:49:20

Time elapsed

4:00:00

Time remaining

0:00:00

Problem B
EvenOdd

Consider the following function $f(X)$, which takes a single positive integer as 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 for any positive integer $X$, this function terminates. Given an interval $[L, R]$, compute the sum

\[ S = f(L) + f(L+1) + \cdots + f(R-1) + f(R)\enspace . \]

Input

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

Output

Output the result $S$ modulo the prime $10^9+7$.

Sample Input 1 Sample Output 1
1 127
1083
Sample Input 2 Sample Output 2
74 74
11