Mari 有三个整数 $$$n$$$、$$$x$$$ 和 $$$y$$$。
如果满足以下条件,则称 $$$a$$$ 为 $$$n$$$ 非负整数的数组为好:
- $$$a_1+a_2+\ldots+a_n=x$$$,并且
- $$$a_1 \, | \, a_2 \, | \、\点\、| \, 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{ times}} \oplus 3 \oplus 3 \oplus 3 = 2$$$。
在第二个测试用例中,没有好的序列。输出应该是$$$0$$$。