题目描述

整数 $N,L,R$ が与えられます． 以下の条件を両方満たす整数 $x$ の個数を数えてください．

• $L\ \leq\ x\ \leq\ R$
• $(x\ \oplus\ N)\ <\ N$ （ここで $\oplus$ はビット単位 $\mathrm{XOR}$ 演算を表す）

ビット単位 $\mathrm{XOR}$ 演算とは 整数 $A,\ B$ のビット単位 $\mathrm{XOR}$ 、$A\ \oplus\ B$ は、以下のように定義されます。

• $A\ \oplus\ B$ を二進表記した際の $2^k$ ($k\ \geq\ 0$) の位の数は、$A,\ B$ を二進表記した際の $2^k$ の位の数のうち一方のみが $1$ であれば $1$、そうでなければ $0$ である。

例えば、$3\ \oplus\ 5\ =\ 6$ となります (二進表記すると: $011\ \oplus\ 101\ =\ 110$)。

输入格式

入力は以下の形式で標準入力から与えられる．

$N$ $L$ $R$

输出格式

答えを出力せよ．

题目大意

给定三个正整数 $N,L,R$，询问满足如下条件的整数 $x$ 的个数：

• $L\leq x\leq R$

• $(x \oplus N) < N$

其中 $\oplus$ 是按位异或运算。

2 1 2

1

10 2 19

10

1000000000000000000 1 1000000000000000000

847078495393153025

提示

制約

• $1\ \leq\ N\ \leq\ 10^{18}$
• $1\ \leq\ L\ \leq\ R\ \leq\ 10^{18}$
• 入力される値はすべて整数である

Sample Explanation 1

$x=1$ の場合，$L\ \leq\ x\ \leq\ R$ は満たしますが，$(x\ \oplus\ N)\ <\ N$ は満たしません． $x=2$ の場合，両方の条件を満たします． 他に条件を満たす $x$ は存在しません．