Description

Yue likes complex numbers very much, especially complex numbers of the form $e^{2\pi it}$. She chooses two positive integers $n,k$, and calls $1+e^{\frac{2\pi i x_1 \dots x_k}{n}}$ the absolute degree of $(x_1,\dots,x_k)$. The product of the absolute degrees of all $(x_1,\dots,x_k)$ satisfying $1 \le x_i \le n$ $(i \in \{1,2,\dots,k\})$ is called the irrelevance degree of $(n,k)$. Now she wants you to help her compute, for each $t \in \{1,2,\dots,k\}$, the irrelevance degree of $(n,t)$, denoted as $ans \bmod{335544323}$. Since it is too troublesome to report too many numbers, you only need to output the result of XOR-ing all answers together.

Input Format

One line with two positive integers $n,k$.

Output Format

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

15 2

201012023

1 3

2

521 6

262795752

6546546546546543 22211

388124125

Hint

Brief statement of the problem:

Given $n,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 ix_1x_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}$, and $i$ is the imaginary unit, satisfying $i^2=-1$.

Sample explanation:

For the first sample, when $t=1,2$, the answers are $2,35184372088832$ respectively. After taking modulo, they are $2,201012021$, and the XOR result is $201012023$.

For the second sample, when $t=1,2,3$, all answers are $2$, and the XOR result is $2$.

Due to space limits, the remaining samples are not explained.

Constraints:

This problem uses bundled testcases. The limits and scores of each subtask are as follows:

Subtask No.	$n \le$	$k \le$	Special constraint	Score
$1$	$10$	$1$	None	$7$
$2$	$1$	$10$
$3$	$10$	$2$
$4$	$10^{18}$	$10^5$	$n$ is even
$5$	$10$		$n^k \le 730$	$16$
$6$	$10^9$	$10^3$	None	$19$
$7$	$10^{18}$	$10^5$		$37$

For $100\%$ of the testdata, $1 \le n \le 10^{18},1 \le k \le 10^5$.

Translated by ChatGPT 5