Problem Description

This problem is an enhanced version of 「Stoi2031」Orchid Pavilion. Original Problem Link

Given \( n = a^b, k \), for \( 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 i x_1 x_2 \dots x_t}{n}} \right) \bmod{335544323} \]

Output the XOR sum of all \( k \) answers.

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

Input Format

A single line containing three positive integers \( a, b, k \), where \( n = a^b \).

Output Format

A single line containing a natural number representing the answer.

Sample Input and Output

Sample Input #1

15 1 2

Sample Output #1

201012023

Sample Input #2

1 7 3

Sample Output #2

2

Sample Input #3

3 2 3

Sample Output #3

301162058

Sample Input #4

4 2 2

Sample Output #4

0

Sample Input #5

19260817 114514 13579

Sample Output #5

461194421

Notes

For all test cases, \( 1 \le a \le 10^{18} \), \( 1 \le b \le 10^{13} \), \( 1 \le k \le 10^5 \).

见题面 Input 部分

见题面 Output 部分