CF1770F.Koxia and Sequence

Mari has three integers $n$, $x$, and $y$.

Call an array $a$ of $n$ non-negative integers good if it satisfies the following conditions:

• $a_1+a_2+\ldots+a_n=x$, and
• $a_1 \, | \, a_2 \, | \, \ldots \, | \, a_n=y$, where $|$ denotes the bitwise OR operation.

The score of a good array is the value of $a_1 \oplus a_2 \oplus \ldots \oplus a_n$, where $\oplus$ denotes the bitwise XOR operation.

Koxia wants you to find the total bitwise XOR of the scores of all good arrays. If there are no good arrays, output $0$ instead.

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

称一个由 $n$ 个非负整数组成的数组 $a$ 是“好的”，当且仅当它满足以下两个条件：

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

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

Koxia 希望你求出所有“好的”数组的得分的按位异或总和。若不存在任何“好的”数组，则输出 $0$。

The first line of input contains three integers $n$, $x$ and $y$ ($1 \leq n \lt 2^{40}$, $0 \leq x \lt 2^{60}$, $0 \leq y \lt 2^{20}$).

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

Output a single integer — the total bitwise XOR of the scores of all good arrays.

输出一个整数——所有好数组的得分的按位异或（XOR）总和。

In the first test case, there are $12$ good arrays totally as follows.

• $[0,2,3]$, $[0,3,2]$, $[2,0,3]$, $[2,3,0]$, $[3,0,2]$ and $[3,2,0]$ — the score is $0 \oplus 2 \oplus 3 = 1$;
• $[1, 2, 2]$, $[2, 1, 2]$ and $[2, 2, 1]$ — the score is $1 \oplus 2 \oplus 2 = 1$;
• $[1, 1, 3]$, $[1, 3, 1]$ and $[3, 1, 1]$ — the score is $1 \oplus 1 \oplus 3 = 3$.

Therefore, the total bitwise xor of the scores is $\underbrace{1 \oplus \ldots \oplus 1}_{9\text{ times}} \oplus 3 \oplus 3 \oplus 3 = 2$.

In the second test case, there are no good sequences. The output should be $0$.

在第一个测试用例中，总共有 $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$。