F - Coincidence

Contest Duration: 2019-08-18(Sun) 12:00 - 2019-08-18(Sun) 13:40 (local time) (100 minutes) Back to Home

F - Coincidence Editorial

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$ である。

例えば、 $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$ で割ったあまりを出力せよ。

入力例 1Copy

Copy

2 3

出力例 1Copy

Copy

条件を満たす組は $(2, 2), (2, 3), (3, 3)$ の $3$ 通りです。

入力例 2Copy

Copy

10 100

出力例 2Copy

Copy

入力例 3Copy

Copy

1 1000000000000000000

出力例 3Copy

Copy

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.

For example, $3 \text{ XOR } 5 = 6$ . (In base two: $011 \text{ XOR } 101 = 110$ .)

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 1Copy

Copy

2 3

Sample Output 1Copy

Copy

Three pairs satisfy the condition: $(2, 2)$ , $(2, 3)$ , and $(3, 3)$ .

Sample Input 2Copy

Copy

10 100

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

1 1000000000000000000

Sample Output 3Copy

Copy

68038601

Be sure to compute the number modulo $10^9 + 7$ .