A quick question is a good question. Calculate the following sum:

~\sum_{x=l}^{r} \text{XOR}(1, 2, ..., x)~

Input

The first line consists of two integers ~l \; r~, representing the parameters for the sum. The following conditions hold:

• ~1 \leq l, r \leq 10^{15}~
• ~1 \leq r - l \leq 10^{6}~

Output

Output the value of the sum.

Note: Since the answer may be very large, return it modulus ~10^9 + 7~.

Example

Input

4 6

Output

12

• ~\text{XOR}(1, 2, ..., 4) = 4~
• ~\text{XOR}(1, 2, ..., 5) = 1~
• ~\text{XOR}(1, 2, ..., 6) = 7~

The sum of these XORs is ~12~, so ~\sum_{x=5}^{7} \text{XOR}(1, 2, ..., x) = 12~.