← 返回题目列表

AtCoder · abc138_f

F. 巧合

中文机器翻译题面 查看原题

分数: 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 否则。
例如, 3 \text{ XOR } 5 = 6。 (在基数二中: 011 \text{ XOR } 101 = 110.)

约束

  • 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.