题目描述

给定整数 $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$）。

约束条件

• $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