F. Кохиа и последовательность
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Мари есть три целых числа $$$n$$$, $$$x$$$ и $$$y$$$.

Назовем массив $$$a$$$ из $$$n$$$ неотрицательных целых чисел хорошим, если он удовлетворяет следующим ограничениям:

  • $$$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$$$ обозначает операцию побитового исключающего ИЛИ.

Косия хочет, чтобы вы нашли побитовое исключающее ИЛИ значений всех хороших массивов. Если хороших массивов не существует, выведите $$$0$$$.

Входные данные

Первая строка содержит три целых числа $$$n$$$, $$$x$$$ и $$$y$$$ ($$$1 \leq n < 2^{40}$$$, $$$0 \leq x < 2^{60}$$$, $$$0 \leq y < 2^{20}$$$).

Выходные данные

Выведите одно целое число — побитовое исключающее ИЛИ значений всех хороших массивов.

Примеры
Входные данные
3 5 3
Выходные данные
2
Входные данные
100 0 100
Выходные данные
0
Входные данные
79877974817 749875791743978 982783
Выходные данные
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]$$$ and $$$[2, 2, 1]$$$: значение равно $$$1 \oplus 2 \oplus 2 = 1$$$;
  • $$$[1, 1, 3]$$$, $$$[1, 3, 1]$$$ and $$$[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$$$.