CF643F.Bears and Juice

There are n bears in the inn and p places to sleep. Bears will party together for some number of nights (and days).

Bears love drinking juice. They don't like wine but they can't distinguish it from juice by taste or smell.

A bear doesn't sleep unless he drinks wine. A bear must go to sleep a few hours after drinking a wine. He will wake up many days after the party is over.

Radewoosh is the owner of the inn. He wants to put some number of barrels in front of bears. One barrel will contain wine and all other ones will contain juice. Radewoosh will challenge bears to find a barrel with wine.

Each night, the following happens in this exact order:

1. Each bear must choose a (maybe empty) set of barrels. The same barrel may be chosen by many bears.
2. Each bear drinks a glass from each barrel he chose.
3. All bears who drink wine go to sleep (exactly those bears who chose a barrel with wine). They will wake up many days after the party is over. If there are not enough places to sleep then bears lose immediately.

At the end, if it's sure where wine is and there is at least one awake bear then bears win (unless they have lost before because of the number of places to sleep).

Radewoosh wants to allow bears to win. He considers q scenarios. In the i-th scenario the party will last for i nights. Then, let R__i denote the maximum number of barrels for which bears surely win if they behave optimally. Let's define . Your task is to find , where denotes the exclusive or (also denoted as XOR).

Note that the same barrel may be chosen by many bears and all of them will go to sleep at once.

旅店中有 $n$ 只熊和 $p$ 个睡觉的位置。这些熊将一起举办持续若干天（及若干夜）的派对。

熊们酷爱喝果汁，但不喜欢葡萄酒；然而，它们无法通过味道或气味区分果汁与葡萄酒。

一只熊只有在饮用了葡萄酒后才会睡觉；并且，它必须在饮用葡萄酒数小时后入睡。它将在派对结束后的许多天之后才醒来。

Radewoosh 是这家旅店的老板。他打算在熊面前放置若干个桶，其中恰好一个桶中装有葡萄酒，其余所有桶中均装有果汁。Radewoosh 将挑战熊们找出装有葡萄酒的那个桶。

每晚，以下事件将严格按此顺序发生：

1. 每只熊必须选择一个（可能为空的）桶集合；同一桶可被多只熊同时选择；
2. 每只熊从自己所选的每个桶中各饮一杯；
3. 所有饮用了葡萄酒的熊立即入睡（即：所有选择了装有葡萄酒的桶的熊）。它们将在派对结束后的许多天之后才醒来。若此时可用的睡觉位置不足，则熊立即失败。

最终，若能确定无疑地指出哪只桶中装有葡萄酒，并且至少还有一只熊处于清醒状态，则熊获胜（除非此前已因睡觉位置不足而失败）。

Radewoosh 希望让熊能够获胜。他考虑了 $q$ 种情形：在第 $i$ 种情形下，派对将持续 $i$ 夜。记 $R_i$ 为：在最优策略下，熊必定获胜的最大桶数。定义
。
你的任务是计算
，
其中

表示异或运算（亦记作 XOR）。

注意：同一桶可被多只熊同时选择，且所有饮用了该桶中葡萄酒的熊将同时入睡。

The only line of the input contains three integers n, p and q (1 ≤ n ≤ 109, 1 ≤ p ≤ 130, 1 ≤ q ≤ 2 000 000) — the number of bears, the number of places to sleep and the number of scenarios, respectively.

输入仅包含一行，三个整数 $n$、$p$ 和 $q$（$1 ≤ n ≤ 10^9$，$1 ≤ p ≤ 130$，$1 ≤ q ≤ 2\,000\,000$），分别表示熊的数量、床位数量和场景数量。

Print one integer, equal to .

输出一个整数，其值等于 。

In the first sample, there are 5 bears and only 1 place to sleep. We have _R_1 = 6, _R_2 = 11, _R_3 = 16 so the answer is . Let's analyze the optimal strategy for scenario with 2 days. There are _R_2 = 11 barrels and 10 of them contain juice.

• In the first night, the i-th bear chooses a barrel i only.
  • If one of the first 5 barrels contains wine then one bear goes to sleep. Then, bears win because they know where wine is and there is at least one awake bear.
  • But let's say none of the first 5 barrels contains wine. In the second night, the i-th bear chooses a barrel 5 + i.
    • If one of barrels 6 – 10 contains wine then one bear goes to sleep. And again, bears win in such a situation.
    • If nobody went to sleep then wine is in a barrel 11.

In the second sample, there is only one bear. He should choose an empty set of barrels in each night. Otherwise, he would maybe get wine and bears would lose (because there must be at least one awake bear). So, for any number of days we have R__i = 1. The answer is .

在第一个样例中，有 5 只熊，但仅有 1 个睡觉的位置。我们有 $R_1 = 6$，$R_2 = 11$，$R_3 = 16$，因此答案为 。我们来分析一下持续 2 天的情形下的最优策略。此时共有 $R_2 = 11$ 个桶，其中 10 个装的是果汁。

• 在第一晚，第 $i$ 只熊仅选择第 $i$ 个桶。
  • 如果前 5 个桶中有一个装的是酒，则有一只熊会去睡觉。此时熊获胜，因为它们已知酒的位置，且至少还有一只熊保持清醒。
  • 但我们假设前 5 个桶中均未装酒。那么在第二晚，第 $i$ 只熊选择第 $5 + i$ 个桶。
    • 如果第 6 至第 10 个桶中有一个装的是酒，则有一只熊会去睡觉；此时熊再次获胜。
    • 如果没有任何熊去睡觉，则酒一定在第 11 个桶中。

在第二个样例中，仅有一只熊。它每晚都应选择一个空的桶集合。否则，它可能喝到酒，从而导致熊失败（因为必须至少有一只熊保持清醒）。因此，对于任意天数，均有 $R_i = 1$。答案为 。