Bears and Juice

- 有 $n$ 只熊和 $p$ 张床，还有若干个无限大的酒桶（至少一个），其中恰好只有一个酒桶里装着酒，其它酒桶里都装着果汁。 - 熊一开始不知道哪桶里面是酒，于是进行了一次挑战，目标是找到哪桶里面是酒。 - 每天，每只还醒着的熊会选择一个酒桶的子集（可以为空集），并且喝下选择的酒桶中的一小杯饮料。 - 如果一只熊喝到了酒，它会上床睡觉一直到挑战结束。但一张床只能容纳一只熊，如果有熊没有床睡觉，则挑战失败。 - 如果 $i$ 天后至少还剩一只熊没睡觉，且能根据前面的线索推理出哪桶里面是酒，则挑战成功。 - 请你求出对于 $i \in [1,q]$，在可以确保挑战成功的情况下，最多有多少个酒桶。 - 设对于 $i$ 的答案为 $R_i$，你需要求出 $\operatorname{xor}_{i=1}^q ((i \times R_i) \bmod 2^{32})$。 - $n \le 10^9$，$p \le 130$，$q \le 2 \times 10^6$。

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.

The only line of the input contains three integers $ n $ , $ p $ and $ q $ ( $ 1<=n<=10^{9} $ , $ 1<=p<=130 $ , $ 1<=q<=2000000 $ ) — the number of bears, the number of places to sleep and the number of scenarios, respectively.

Print one integer, equal to .

5 1 3

32

1 100 4

4

3 2 1

7

100 100 100

381863924

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 .