|VK Cup 2016 - Round 3|
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:
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 Ri 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.
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.
Print one integer, equal to .
5 1 3
1 100 4
3 2 1
100 100 100
In the first sample, there are 5 bears and only 1 place to sleep. We have R1 = 6, R2 = 11, R3 = 16 so the answer is . Let's analyze the optimal strategy for scenario with 2 days. There are R2 = 11 barrels and 10 of them contain juice.
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 Ri = 1. The answer is .