题目描述

给定整数 $N, L, R$。请计算满足以下两个条件的整数 $x$ 的个数。

• $L \leq x \leq R$
• $(x \oplus N) < N$（其中 $\oplus$ 表示按位异或运算）

按位异或运算的定义如下：对于整数 $A, B$，它们的按位异或 $A \oplus B$ 定义为：

• $A \oplus B$ 的二进制表示中，第 $2^k$ 位（$k \geq 0$）的数，如果 $A, B$ 的二进制表示在该位上只有一个为 $1$，则结果为 $1$，否则为 $0$。

例如，$3 \oplus 5 = 6$（二进制表示为：$011 \oplus 101 = 110$）。

输入格式

输入从标准输入中给出，格式如下：

$N$ $L$ $R$

输出格式

请输出答案。

样例 1

输入

2 1 2

输出

1

样例 2

输入

10 2 19

输出

10

样例 3

输入

1000000000000000000 1 1000000000000000000

输出

847078495393153025

说明/提示

限制条件

• $1 \leq N \leq 10^{18}$
• $1 \leq L \leq R \leq 10^{18}$
• 输入的所有值均为整数

样例解释 1

当 $x=1$ 时，$L \leq x \leq R$ 成立，但 $(x \oplus N) < N$ 不成立。当 $x=2$ 时，两个条件都成立。没有其他满足条件的 $x$。

由 ChatGPT 4.1 翻译