Nazar, a student of the scientific lyceum of the Kingdom of Kremland, is known for his outstanding mathematical abilities. Today a math teacher gave him a very difficult task.

Consider two infinite sets of numbers. The first set consists of odd positive numbers (1, 3, 5, 7, …), and the second set consists of even positive numbers (2, 4, 6, 8, …). At the first stage, the teacher writes the first number on the endless blackboard from the first set, in the second stage — the first two numbers from the second set, on the third stage — the next four numbers from the first set, on the fourth — the next eight numbers from the second set and so on. In other words, at each stage, starting from the second, he writes out two times more numbers than at the previous one, and also changes the set from which these numbers are written out to another. 

The ten first written numbers: 1, 2, 4, 3, 5, 7, 9, 6, 8, 10. Let's number the numbers written, starting with one.

The task is to find the sum of numbers with numbers from l to r for given integers l and r. The answer may be big, so you need to find the remainder of the division by 1000000007 (10^9+7).

Nazar thought about this problem for a long time, but didn't come up with a solution. Help him solve this problem.

Input

The first line contains two integers l and r (1 ≤ l ≤ r ≤ 10^{18}) — the range in which you need to find the sum.

Output

Print a single integer — the answer modulo 1000000007 (10^9+7).

Examples

Input


1 3


Output


7

Input


5 14


Output


105

Input


88005553535 99999999999


Output


761141116

Note

In the first example, the answer is the sum of the first three numbers written out (1 + 2 + 4 = 7).

In the second example, the numbers with numbers from 5 to 14: 5, 7, 9, 6, 8, 10, 12, 14, 16, 18. Their sum is 105.
MOD = 10**9 + 7
def main():
    l,r = [int(x) for x in input().split()]
    

    def cumodd(l):
        return ((l+1)//2)**2
    
    def cumeven(l):
        n = l//2
        return n*(n+1)
    
    # sum of odd [l to odd r)
    def sumodd(l,r):
        return cumodd(r-2) - cumodd(l - 2)
    def sumeven(l,r):
        return cumeven(r-2) - cumeven(l - 2)
    
    # sum of numbs < x
    def cumsum(x):
        s = 0

        next_odd = 1
        next_even = 2
        step = 1
        odd = True
        cur_ind = 0
        while cur_ind + step <= x:
            if odd:
                s += sumodd(next_odd,next_odd + 2*step)
                next_odd += 2*step
            else:
                s += sumeven(next_even, next_even + 2*step)
                next_even += 2*step

            cur_ind += step
            step *= 2
            odd = not odd
        
        if odd:
            s += sumodd(next_odd, next_odd + 2*(x-cur_ind))
        else:
            s += sumeven(next_even, next_even + 2*(x-cur_ind))
        return s
    
    print (cumsum(r) - cumsum(l-1))%MOD 
        


######## Python 2 and 3 footer by Pajenegod and c1729 

py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
    from cStringIO import StringIO as BytesIO
else:
    from io import BytesIO
    __str__ = str
    str = lambda x=b'': x if type(x) is bytes else __str__(x).encode()

import os, sys
from io import IOBase

BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._buffer = BytesIO()
        self._file = file
        self._fd = file.fileno()
        self._writable = "x" in file.mode or "w" in file.mode
        if self._writable: self.write = self._buffer.write

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        b = self._buffer; b.seek((b.tell(), b.seek(0,2), b.write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return self._buffer.read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return self._buffer.readline()

    def flush(self):
        if self._writable:
            os.write(self._fd, self._buffer.getvalue())
            self._buffer.truncate(0), self._buffer.seek(0)

sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip(b'\r\n')

# Cout implemented in Python
import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = b'\n'

# Read all remaining integers in stdin, type is given by optional argument, this is fast
def readnumbers(self, zero=0):
    conv = ord if py2 else lambda x:x
    A = []; numb = zero; sign = 1; i = 0; s = sys.stdin.read()
    try:
        while True:
            if s[i] >= b'0' [0]:
                numb = 10 * numb + conv(s[i]) - 48
            elif s[i] == b'-' [0]: sign = -1
            elif s[i] != b'\r' [0]:
                A.append(sign*numb)
                numb = 0; sign = 1
            i += 1
    except:pass
    if s and s[-1] >= b'0' [0]:
        A.append(sign*numb)
    return A

if __name__== "__main__":
  main()
