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.

Input

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}$).

Output

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

Note

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