题目背景

本题是「Stoi2031」兰亭序 的加强版。

题目描述

给定 $n=a^b,k$，对 $1 \le t \le k$ 求

输出所有 $k$ 个答案的异或和。

其中 $e^{it}=\cos{t}+i\sin{t}$ 对所有 $t \in \mathbb{R}$ 成立，$i$ 为虚数单位，满足 $i^2=-1$。

输入格式

一行三个正整数 $a,b,k$，其中 $n=a^b$。

输出格式

一行一个自然数表示答案。

15 1 2

201012023

1 7 3

2

3 2 3

301162058

4 2 2

0

19260817 114514 13579

461194421

提示

对于所有数据，$1 \le a \le 10^{18}$，$1 \le b \le 10^{13}$，$1 \le k \le 10^5$。