余数等于异或

题目描述

给定整数 $L, R$。求满足 $L \leq x \leq y \leq R$ 且 $y$ 除以 $x$ 的余数等于 $y \text{ XOR } x$ 的整数对 $(x, y)$ 的个数，并输出其除以 $10^9 + 7$ 的余数。

什么是 $\text{ XOR }$

整数 $A, B$ 的按位异或 $a \text{ XOR } b$ 定义如下：

• 将 $a \text{ XOR } b$ 用二进制表示时，$2^k$（$k \geq 0$）位上的数字，在 $A, B$ 的二进制表示中 $2^k$ 位上的数字只有一方为 $1$ 时为 $1$，否则为 $0$。

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

输入格式

输入按以下格式从标准输入给出：

$L$ $R$

输出格式

输出满足条件的整数对 $(x, y)$（$L \leq x \leq y \leq R$）的个数除以 $10^9 + 7$ 的余数。

样例

2 3

3

满足条件的数对有 $(2, 2), (2, 3), (3, 3)$ 这 $3$ 组。

10 100

604

1 1000000000000000000

68038601

不要忘记计算个数除以 $10^9 + 7$ 的余数。

数据范围

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