問題文

整数 $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$)。

制約

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

入力

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

$N$ $L$ $R$

出力

答えを出力せよ．

入力例 1

2 1 2

出力例 1

1

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

入力例 2

10 2 19

出力例 2

10

入力例 3

1000000000000000000 1 1000000000000000000

出力例 3

847078495393153025