Koxia 与序列

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

Mari 有三个整数 $n$、$x$ 和 $y$。

如果一个长度为 $n$ 的非负整数数组 $a$ 满足以下条件，则称其为“好数组”：

• $a_1 + a_2 + \ldots + a_n = x$；
• $a_1 \mid a_2 \mid \ldots \mid a_n = y$，其中 $|$ 表示按位或运算。

一个好数组的得分定义为 $a_1 \oplus a_2 \oplus \ldots \oplus a_n$，其中 $\oplus$ 表示按位异或运算。

Koxia 想让你求出所有好数组得分的总异或值。如果不存在好数组，则输出 $0$。

输入格式

输入的第一行包含三个整数 $n$、$x$ 和 $y$（$1 \leq n < 2^{40}$，$0 \leq x < 2^{60}$，$0 \leq y < 2^{20}$）。

输出格式

输出一个整数，表示所有好数组得分的总异或值。

样例输入 1

3 5 3

样例输出 1

2

样例输入 2

100 0 100

样例输出 2

0

样例输入 3

79877974817 749875791743978 982783

样例输出 3

64

提示

在第一个测试用例中，总共有 $12$ 个好数组，如下所示：

• $[0,2,3]$、$[0,3,2]$、$[2,0,3]$、$[2,3,0]$、$[3,0,2]$ 和 $[3,2,0]$ —— 得分为 $0 \oplus 2 \oplus 3 = 1$；
• $[1,2,2]$、$[2,1,2]$ 和 $[2,2,1]$ —— 得分为 $1 \oplus 2 \oplus 2 = 1$；
• $[1,1,3]$、$[1,3,1]$ 和 $[3,1,1]$ —— 得分为 $1 \oplus 1 \oplus 3 = 3$。

因此，总异或值为 $\underbrace{1 \oplus \ldots \oplus 1}_{9\text{ 次}} \oplus 3 \oplus 3 \oplus 3 = 2$。

在第二个测试用例中，没有好数组，输出应为 $0$。

数据范围

$1\le n<2^{40}$，$0\le x<2^{60}$，$0\le y<2^{20}$。