熊与果汁

• 时间限制：5 秒
• 内存限制：256 MiB

题目描述

旅店中有 $n$ 只熊和 $p$ 个床位。主人会摆出若干桶饮料，其中恰好一桶是葡萄酒，其余都是果汁。熊无法通过味道或气味分辨两种饮料。

每个夜晚依次发生以下事情：

1. 每只仍醒着的熊选择一个桶的集合，这个集合可以为空，不同熊可以选择同一桶；
2. 每只熊从自己选择的每个桶中喝一杯；
3. 所有选择了葡萄酒桶的熊都会睡着，并且在聚会结束前不再醒来。若睡着的熊总数超过 $p$，熊立即失败。

聚会结束时，如果熊能够唯一确定哪一桶是葡萄酒，并且至少有一只熊仍然醒着，那么熊获胜。熊会采用最优策略。

主人考虑 $q$ 种场景。第 $i$ 种场景持续 $i$ 个夜晚。令 $R_i$ 表示在第 $i$ 种场景中，熊能够保证获胜的最多桶数。定义

请计算

其中 $\oplus$ 表示按位异或。

输入格式

输入仅一行，包含三个整数 $n,p,q$，分别表示熊的数量、床位数量和场景数量。

输出格式

输出一个整数，表示所求异或值。

样例输入 1

5 1 3

样例输出 1

32

样例输入 2

1 100 4

样例输出 2

4

样例输入 3

3 2 1

样例输出 3

7

样例输入 4

100 100 100

样例输出 4

381863924

数据范围

对于所有数据，$1\le n\le10^9$，$1\le p\le130$，$1\le q\le2\times10^6$。