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.
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""Codeforces Round #553 (Div. 2)

Problem C. Problem for Nazar

:author:         Kitchen Tong
:mail:    kctong529@gmail.com

Please feel free to contact me if you have any question
regarding the implementation below.
"""

__version__ = '1.1'
__date__ = '2019-04-19'

import sys
from math import log


def sum_odd(n, mod, inclusive=True):
    '''
    The integer n refers to the number of terms in the sequence:
        [1, 3, 5, 7, 9, ..., 2n-3, 2n-1]
    The sum of consecutive integers:
        [1, 2, 3, 4, 5, ..., n-1, n]
    is given by:
        n (n + 1) / 2
    Multiply the sequence by factor of 2:
        [2, 4, 6, 8, 10, ..., 2n-2, 2n]
    which has the sum:
        n (n + 1)
    and then subtract the sum by n would be the answer
    Hence the sum we want is:
        n (n + 1) - n
      = n^2
    '''
    answer = pow(n, 2, mod)
    if not inclusive:
        return (answer - 2 * n + 1) % mod
    return answer

def sum_even(n, mod, inclusive=True):
    '''
    As stated in the docstring of sum_odd(n),
    and now we want the sum of sequence:
        [2, 4, 6, 8, 10, ..., 2n-2, 2n]
    which is given as:
        n (n + 1)
      = n^2 + n
    '''
    answer = pow(n, 2, mod) + n
    if not inclusive:
        return (answer - 2 * n) % mod
    return answer

def sum_geometric(a, r, n):
    '''
    Consider the following sequence:
        [1, 2, 4, 3, 5, 7, 9, 6, 8, 10, 12, 14, 16, 18, 20, 11, ...]
    Take a close look at the odd sequences:
        [1], [3, 5, 7, 9], [11, 13, 15, ..., 39, 41]
         1        4                     16
    and the even sequences:
        [2, 4], [6, 8, 10, ..., 18, 20], [22, 24, ..., 82, 84]
          2                 8                     32
    And observe that the length of sequence grows by factor of 4.
    Therefore, to obtain the total length of all
    corresponding (odd/even) sequences:
        a (r^n - 1) / (r - 1)
    where r = 4,
          n = number of groups or sequences
          a = 1 if it's odd sequence, or
            = 2 if it's even sequence
    '''
    if n == 1:
        return a
    return a * (pow(r, n) - 1) // (r-1)

def sum_all_previous(lr, mod, inclusive=True):
    '''
    First find the group in which lr is located,
    and count the number of elements in each of odd and even groups.
    Then we can find the sum of all elements in both groups.

    Consider the following sequence:
        [1, 2, 4, 3, 5, 7, 9, 6, 8, 10, 12, 14, 16, 18, 20, 11, ...]
                                         (lr is here)

    Assume lr is in an even group,
    the immediate previous group is then an odd group.
    (the same can be done vice versa)

    The number of groups before it can be found with:
        idx = log_2(lr) rounded down to integer,
        
        [1, 2, 4, 3, 5, 7, 9, 6, 8, 10, 12, 14, 16, 18, 20, 11, ...]
      (one)( two)(  three   )(          four              )(five...)

    e.g. If there are 3 groups, 2 of them are odd. (idx: 3 -> n: 2)
         If there are 4 groups, 2 of them are even. (idx: 4 -> n: 2)

    Hence, the number of odd groups among those is:
        n = (idx + 1) / 2 rounded down to integer.

    When the number of odd groups is known,
    the number of odd elements can be found using geometric sequence.
    All of the rest would then be even elements.
    '''
    idx = int(log(lr, 2))
    n = (idx + 1) // 2
    if n < 1:    # if it is group 1 or group 2
        if inclusive:
            return (0, 1, 3, 7)[lr]
        return (0, 1, 3, 7)[lr-1]
    if idx % 2 == 1:    # if previous group is odd group
        odds = sum_geometric(1, 4, n)
        evens = lr - odds
        return sum_odd(odds, mod) + sum_even(evens, mod, inclusive)

    else:
        evens = sum_geometric(2, 4, n)
        odds = lr - evens
        return sum_even(evens, mod) + sum_odd(odds, mod, inclusive)
    return -1

def solve(l, r, mod):
    '''
    Use the same function for l and r,
    where the only difference is the inclusion criteria.
    '''
    return (sum_all_previous(r, mod)
            - sum_all_previous(l, mod, inclusive=False)) % mod

def main(argv=None):
    l, r = map(int, input().split())
    mod = 1000000007
    print(solve(l, r, mod))
    return 0

if __name__ == "__main__":
    STATUS = main()
    sys.exit(STATUS)

