Description

As everyone knows, the standard prime factorization form of $i$ is $\prod\limits_{j=1}^{k_i} p_{i,j}^{c_{i,j}}$.

Given a sequence $a$ of length $n$.

Define $f(x)=\sum\limits_{d|x}\left({a_{\frac{x}{d}}\times\prod\limits_{i=1}^{k_d}{C_{c_{d,i}+m}^{m}}}\right)$. Now you need to compute $f(1),f(2),f(3),\cdots,f(n)$, where $m$ is a given constant.

Since monsters does not like numbers that are too large, you need to output the answers modulo $998244353$.

In addition, to avoid excessive input and output size, this problem uses a random number generator to produce the data, and you only need to output the XOR of all answers.

If you do not know what $C$ is, $C_n^m=\dfrac{n!}{m!(n-m)!}$, where $!$ denotes factorial.

Input Format

There is one line of input.

The first line contains three non-negative integers $n,m,seed$.

You need to call the data generator (randomdigit) $n$ times in your program to obtain $a$.

Output Format

Output one line with one integer: the XOR of all $f(x)$.

3 0 12345678

175092810

114514 100000 1919810

212218651

9919810 2 12121121

204065242

Hint

Data Generator

C/C++:

#define uint unsigned int
uint seed;
inline uint randomdigit(){
	seed^=seed<<13;
	seed^=seed>>17;
	seed^=seed<<5;
	return seed;
}

pascal:

var seed:dword;
function randomdigit:dword;
begin
	seed:=seed xor(seed shl 13);
	seed:=seed xor(seed shr 17);
	seed:=seed xor(seed shl 5);
	randomdigit:=seed;
end;

python3:

seed = 0 # please input seed
mod = 1 << 32
def randomdigit():
    global seed
    seed ^= (seed << 13) % mod
    seed ^= (seed >> 17) % mod
    seed ^= (seed << 5) % mod
    return seed

Sample Explanation

The sequence $a$ is $506005380,3857352168,531380003$.

The values of $f(1),f(2),f(3)$ modulo $998244353$ are $506005380,370380136,39141030$, respectively.

Constraints

For $100\%$ of the testdata, $0\le m\le 10^5$, $1\le n\le 10^7$, and $0\le a_1,a_2,\cdots,a_n,seed<2^{32}$.

• Subtask $1$ ($30\%$ of the testdata): $n\le 10^6$, $m\le 10^5$.

  In this subtask:

  There is $10\%$ of the testdata with $m=0$.

  Another $10\%$ of the testdata satisfies $n\le 100$.

• Subtask $2$ (the remaining $70\%$ of the testdata): $n\le 10^7$, $m\le 3$.

Hint

Please pay attention to the impact of memory limits and constant factors on program running efficiency.

Translated by ChatGPT 5