Exponential Product XOR

Given three integers a, b, and k, define n as \(n=a^b\). For each integer \(t\) with \(1 \le t \le k\), compute

[ P(t)=\prod_{x_1=1}^{n}\prod_{x_2=1}^{n}\cdots\prod_{x_t=1}^{n}\Bigl(1+e^{\frac{2\pi i,x_1x_2\cdots x_t}{n}}\Bigr)\bmod 335544323. ]

Here, the complex exponential is defined as \(e^{i\theta}=\cos\theta+ i\sin\theta\) for any real \(\theta\), and \(i\) is the imaginary unit with \(i^2=-1\).

It can be shown that when n is even, at least one factor in each product is zero so that \(P(t)=0\) for all \(t\). When n is odd one may prove that \(P(t) = 2^{n^{t-1}} \bmod 335544323\) for every \(t\ge1\).

Your task is to output the bitwise XOR of all \(k\) answers, i.e. compute

[ Answer = P(1) \oplus P(2) \oplus \cdots \oplus P(k), ]

where \(\oplus\) denotes the bitwise XOR operation.

inputFormat

The input consists of a single line containing three space-separated integers: a, b, and k.

It is guaranteed that a and b are such that \(n=a^b\) fits the conditions described in the problem. (Note: only the parity of n is needed to decide the outcome.)

outputFormat

Output a single integer which is the XOR of all answers \(P(1)\oplus P(2)\oplus \cdots \oplus P(k)\) computed modulo 335544323.

sample

2 1 3

0