F. Медведи и сок
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В гостинице поселились n медведей, но там есть только p спальных мест. Медведи планируют закатить большую вечеринку на несколько ночей (и дней).

Медведи любят пить сок. Они не любят вино, но не могут отличить его от сока ни по вкусу, ни по запаху.

Медведь ложится спать, только если он выпил вина, при этом он уходит спать через несколько часов после этого. Он проснётся только спустя много дней, когда вечеринка уже будет окончена.

Хозяин гостиницы Радевуш хочет предложить медведям несколько бочек с напитками. При этом ровно одна бочка будет содержать вино, а в остальных будет содержаться сок. После этого Радевуш предложит медведям определить, в какой бочке находится вино.

Каждую ночь происходит следующее (ровно в таком порядке):

  1. Каждый медведь выбирает какой-то (возможно, пустой) набор бочек. Одна и та же бочка может быть выбрана несколькими медведями.
  2. Каждый медведь выпивает по одному стакану из каждой бочки, которую он выбрал.
  3. Все медведи, пившие вино, отправляются спать (то есть те медведи, у которых в множестве выбранных бочек была бочка с вином). Они просыпаются спустя много дней, когда вся вечеринка уже окончена. Если свободных спальных мест недостаточно, то медведи автоматически проигрывают.

В конце вечеринки, если однозначно можно определить, в какой бочке находится вино, и хотя бы один медведь не спит, то медведи выигрывают (если, конечно, они не проиграли раньше, потому что кому-то не хватило спальных мест).

Радевуш хотел бы, чтобы медведи выиграли. Он рассматривает q сценариев игры. В i-м сценарии вечеринка продолжается i ночей. Далее пусть Ri обозначает максимальное количество бочек, для которого медведи точно смогут выиграть, если будут действовать оптимально. Обозначим . Вам требуется вычислить , где означает побитовое исключающее или (также известное как XOR).

Обратите внимание, что одна и та же бочка может быть выбрана несколькими медведями и все они одновременно пойдут спать, если она содержит вино.

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

В единственной строке входных данных записаны три целых числа n, p и q (1 ≤ n ≤ 109, 1 ≤ p ≤ 130, 1 ≤ q ≤ 2 000 000) — количество медведей, количество спальных мест и количество сценариев соответственно.

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

Выведите единственное целое число, равное .

Примеры
Входные данные
5 1 3
Выходные данные
32
Входные данные
1 100 4
Выходные данные
4
Входные данные
3 2 1
Выходные данные
7
Входные данные
100 100 100
Выходные данные
381863924
Примечание

В первом примере в гостинице находятся 5 медведей и есть только 1 спальное место. Имеем R1 = 6, R2 = 11, R3 = 16, так что ответ равен . Проанализируем стратегию для сценария с 2 днями. Всего есть R2 = 11 бочек, и 10 из них содержат сок.

  • В первую ночь i-й медведь выбирает бочку i.
    • Если одна из 5 бочек содержит вино, то соответствующий медведь отправится спать. Таким образом, медведи выигрывают, потому они теперь знают где находится вино и есть хотя бы один не спящий медведь.
    • Если никто из 5 медведей не ушёл спать, то на вторую ночь i-й медведь пьёт из бочки 5 + i.
      • Если хотя бы одна из бочек 6 – 10 содержит вино, то соответствующий медведь отправится спать, и медведи победят.
      • Если никто из медведей опять не уйдёт спать, то они точно будут знать, что вино находится в бочке 11.

Во втором примере есть только один медведь. Он не может ничего пить (то есть он выбирает пустое множество бочек каждую ночь), потому что если он уйдёт спать, то медведи сразу проигрывают. Таким образом, для любого числа дней Ri = 1 и ответ равен .