p02938 AtCoder Beginner Contest 138 - Coincidence_32044
Given are integers L and R. Find the number, modulo 10^9 + 7, of pairs of integers (x, y) (L \leq x \leq y \leq R) such that the remainder when y is divided by x is equal to y \mbox{ XOR } x.

What is \mbox{ XOR }?

The XOR of integers A and B, A \mbox{ XOR } B, is defined as follows:

* When A \mbox{ XOR } B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if either A or B, but not both, has 1 in the 2^k's place, and 0 otherwise.

For example, 3 \mbox{ XOR } 5 = 6. (In base two: 011 \mbox{ XOR } 101 = 110.)

Constraints

* 1 \leq L \leq R \leq 10^{18}

Input

Input is given from Standard Input in the following format:


L R


Output

Print the number of pairs of integers (x, y) (L \leq x \leq y \leq R) satisfying the condition, modulo 10^9 + 7.

Examples

Input

2 3


Output

3


Input

10 100


Output

604


Input

1 1000000000000000000


Output

68038601
#!/usr/bin/env python

from collections import deque, defaultdict
import itertools as ite
import sys
import math
import decimal

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

L_, R_ = map(int, raw_input().split())

ans = 0
for MSB in range(70):
    S = 2 ** MSB
    if S * 2 <= L_ or R_ < S:
        continue
    L, R = L_, R_
    if L <= S:
        L = S
    if 2 * S - 1 <= R:
        R = 2 * S - 1
    n1 = nL = nR = 0
    nLR = 1
    SL = SR = 1
    for i in range(MSB)[::-1]:
        flag1 = ((1 << i) & L != 0)
        flag2 = ((1 << i) & R != 0)
        SL *= 2
        SR *= 2
        SL += flag1
        SR += flag2
        n1 *= 3
        if flag1 and not flag2:
            nLR = 0
        if SR - SL >= 2:
            n1 += SR / 2 - SL / 2 - 1
            if not flag1:
                n1 += nL
            if flag2:
                n1 += nR
            if not flag1:
                nL *= 2
                nL += 1
            if flag2:
                nR *= 2
                nR += 1
            if not flag1 and flag2:
                nL += nLR
                nR += nLR
    if L == R:
        ans += 1
    else:
        ans += n1 + (SR - SL + 1) + nL + nR + nLR
print ans % MOD
