分数: 600 点
问题陈述
给定的是整数 L 和 R。求模数 10^9 + 7,整数对 (x, y) (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 书写,即 2^k的地点 (k \geq 0)是 1 如果 A or B,但不是两者都有 1 在 2^k的地点,以及 0 否则。
约束
- 1 \leq L \leq R \leq 10^{18}
输入
输入由标准输入按以下格式给出:
L R
输出
打印整数对的数量 (x, y) (L \leq x \leq y \leq R) 满足条件,取模 10^9 + 7.
示例输入 1
2 3
示例输出 1
3
三对满足条件: (2, 2), (2, 3),和 (3, 3).
示例输入 2
10 100
示例输出 2
604
示例输入 3
1 1000000000000000000
示例输出 3
68038601
一定要计算模数 10^9 + 7.