CF643F Bears and Juice

有 $n$ 只熊在旅店中，旅店里有 $p$ 个睡觉的床位。熊们会一起狂欢若干个夜晚（和白天）。 熊非常喜欢喝果汁。他们不喜欢葡萄酒，但他们无法从味道或气味上分辨葡萄酒和果汁。 熊只有喝了葡萄酒才会去睡觉。在喝完葡萄酒后的几个小时内，熊必须去睡觉。他们会在聚会结束后的许多天才醒来。 Radewoosh 是旅店的老板。他打算在熊们面前摆出若干桶酒。只有一桶里有葡萄酒，其他桶都装的是果汁。Radewoosh 会让熊们找出那桶葡萄酒。 每个夜晚，按以下顺序进行： 1. 每只熊必须选择一个（可以为空的）桶的集合。可以有多只熊选同一桶。 2. 每只熊从自己选的每一桶中喝一杯。 3. 所有喝到葡萄酒的熊都去睡觉（即恰好那些选择了装有葡萄酒桶的熊）。他们会在聚会结束后的许多天才醒来。如果没有足够的睡觉床位，则熊们立即失败。 最终，只要确定知道哪桶里有葡萄酒，并且至少还有一只熊醒着，熊们就获胜（除非之前因为床位数不够已经失败）。 Radewoosh 希望让熊们获胜。他考虑了 $q$ 种场景。在第 $i$ 种场景下，聚会会持续 $i$ 个夜晚。记 $R_i$ 表示如果熊们采用最优策略，能够保证胜利时最多能有多少桶酒。令  你的任务是计算  其中  表示异或运算（XOR）。 注意，同一个桶可以被多只熊选择，并且所有选择了含有葡萄酒桶的熊会同时入睡。

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

输出一行一个整数，表示  的值。

在第一个样例中，有 $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$。答案是 。 由 ChatGPT 5 翻译