题目描述

Given are integers $L$ and $R$. Find the number, mod $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 \text{ XOR } x$.

What is $\text{ XOR }$?

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

• When $A \text{ 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 \text{ XOR } 5 = 6$. (In base two: $011 \text{ XOR } 101 = 110$.)

给出整数 $L$ 和 $R$ 。求模为 $10^9 + 7$ 的一对整数 $(x, y)$ 中，当 $y$ 除以 {49761536} 时有余数的个数。 $(L \leq x \leq y \leq R)$ ，使得 $y$ 除以 $x$ 的余数等于 $y \text{ XOR } x$ 。

$\text{ XOR }$ 是多少？?

整数 $A$ 与 $B$ , $A \text{ XOR } B$ 的 XOR 定义如下：

• 当以二进制写入 $A \text{ XOR } B$ 时，如果 $A$ 或 $B$ （而不是两者）的 $2^k$ 的 $2^k$ 位上有 $1$ ，那么 $k \geq 0$ 位上的数字就是 $1$ ，否则就是 $0$ 。

例如， $3 \text{ XOR } 5 = 6$ 。(二进制： $011 \text{ XOR } 101 = 110$ ）。

输入格式

输入内容按以下格式标准输入：

$L$ $R$

输出格式

打印满足条件的一对整数 $(x, y)$ $(L \leq x \leq y \leq R)$ 的个数。 $(L \leq x \leq y \leq R)$ 满足条件，模数 $10^9 + 7$ .

样例 #1

样例输入 #1

2 3

样例输出 #1

3

样例 #2

样例输入 #2

10 100

样例输出 #2

604

样例 #3

样例输入 #3

1 1000000000000000000

样例输出 #3

68038601

说明

数据规模与约定

• $1 \leq L \leq R \leq 10^{18}$

样例 $1$ 解释

有三对符合条件： $(2, 2)$ 、 $(2, 3)$ 和 $(3, 3)$ 。

样例 $3$ 解释

请务必计算 $10^9 + 7$ 的模数。