Problem Background

Beyond the winds and the moon, I pen a preface awaiting your return. With a stroke of the brush, I end the tale, where the shoreline waves pile up. How to interpret the word "love"? No matter how I write, it seems wrong. What I lack is your understanding of my life. — "Orchid Pavilion Preface"

Problem Description

Yue loves complex numbers, especially those of the form \( e^{2\pi it} \). She has chosen two positive integers \( n \) and \( k \), and defines \( 1 + e^{\frac{2\pi i x_1 \dots x_k}{n}} \) as 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 \) for \( i \in \{1, 2, \dots, k\} \) is called the irrelevance degree of \( (n, k) \). Now, she wants you to help her compute the irrelevance degree \( ans \bmod{335544323} \) for \( t \in \{1, 2, \dots, k\} \). Since answering too many numbers is cumbersome, you only need to provide the result of the XOR operation on all answers.

Input Format

A single line containing two positive integers \( n \) and \( k \).

Output Format

A single line containing a natural number representing the answer.

Sample Input and Output

Input Sample #1

15 2

Output Sample #1

201012023

Input Sample #2

1 3

Output Sample #2

2

Input Sample #3

521 6

Output Sample #3

262795752

Input Sample #4

6546546546546543 22211

Output Sample #4

388124125

Notes/Hints

Simplified Problem Statement:

Given \( n \) and \( 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.

Where \( 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 \) and \( 35184372088832 \), respectively, after modulo operation, they become \( 2 \) and \( 201012021 \), and their XOR sum is \( 201012023 \).

For the second sample, when \( t = 1, 2, 3 \), the answers are all \( 2 \), and their XOR sum is \( 2 \).

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

Data Range:

This problem uses subtask testing, with the constraints and scores for each subtask as follows:

For 100% of the data, \( 1 \le n \le 10^{18}, 1 \le k \le 10^5 \).

见题面 Input 部分

见题面 Output 部分