Background

This problem is an enhanced version of "Stoi2031" Lantingxu.

Problem Description

Given $n=a^b$ and $k$, for each $1 \le t \le k$, compute

$$\prod_{x_1=1}^{n}\prod_{x_2=1}^{n}\dots\prod_{x_t=1}^{n}\left( 1+e^{\frac{2\pi ix_1x_2\dots x_t}{n}} \right) \bmod{335544323}$$

Output the bitwise XOR of all $k$ answers.

Here, $e^{it}=\cos{t}+i\sin{t}$ holds for all $t \in \mathbb{R}$. $i$ is the imaginary unit, satisfying $i^2=-1$.

Input Format

One line with three positive integers $a,b,k$, where $n=a^b$.

Output Format

One line with one non-negative integer representing the answer.

15 1 2

201012023

1 7 3

2

3 2 3

301162058

4 2 2

0

19260817 114514 13579

461194421

Hint

Constraints: For all testdata, $1 \le a \le 10^{18}$, $1 \le b \le 10^{13}$, $1 \le k \le 10^5$.

Translated by ChatGPT 5