/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
整数 L, R が与えられます。整数の組 (x, y) (L \leq x \leq y \leq R) であって、y を x で割った余りが y \text{ XOR } x に等しいものの個数を 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 である。
制約
- 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) の 3 通りです。
入力例 2
10 100
出力例 2
604
入力例 3
1 1000000000000000000
出力例 3
68038601
個数を 10^9 + 7 で割ったあまりを計算することを忘れないでください。
Score : 600 points
Problem Statement
Given are integers L and R. Find the number, modulo 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.
Constraints
- 1 \leq L \leq R \leq 10^{18}
Input
Input is given from Standard Input in the following format:
L R
Output
Print the number of pairs of integers (x, y) (L \leq x \leq y \leq R) satisfying the condition, modulo 10^9 + 7.
Sample Input 1
2 3
Sample Output 1
3
Three pairs satisfy the condition: (2, 2), (2, 3), and (3, 3).
Sample Input 2
10 100
Sample Output 2
604
Sample Input 3
1 1000000000000000000
Sample Output 3
68038601
Be sure to compute the number modulo 10^9 + 7.