题目描述

给定整数 $L, R$。请计算满足以下条件的整数对 $(x, y)$ 的个数，并对 $10^9 + 7$ 取模：

• $L \leq x \leq y \leq R$；
• $y$ 除以 $x$ 的余数等于 $y \text{ XOR } x$。

这里，$\text{XOR}$ 表示按位异或运算。对于整数 $A, B$，$A \text{ XOR } B$ 的定义如下：

• $A \text{ XOR } B$ 的二进制表示中，第 $2^k$ 位（$k \geq 0$）为 $1$ 当且仅当 $A, B$ 的二进制表示中第 $2^k$ 位中恰有一个为 $1$，否则为 $0$。

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

输入格式

输入从标准输入读取，格式如下：

$L$ $R$

输出格式

输出满足条件的整数对 $(x, y)$ 的个数，对 $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$ 种。

样例解释 3

不要忘记对 $10^9 + 7$ 取模。