题目背景

monsters 喜欢因数，所以他要出一道关于因数的题。

题目描述

众所周知，$i$ 的标准分解形式为：$\prod\limits_{j=1}^{k_i}p_{i,j}^{c_{i,j}}$。

给定一个序列 $a$，长度为 $n$。

定义 $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)$，现在需要你求出 $f(1),f(2),f(3),\cdots ,f(n)$，其中 $m$ 是给定常数。

由于 monsters 不喜欢太大的数，他需要你输出答案模 $998244353$ 的值。

另外，为了避免过大的输入输出量，本题使用随机数生成数据，并且只需要你输出所有答案的异或和。

如果你不知道 $C$ 是什么，$C_n^m=\dfrac{n!}{m!(n-m)!}$，其中 $!$ 代表阶乘。

输入格式

输入共有一行。

第一行，三个非负整数 $n,m,seed$。

你需要在程序中调用 $n$ 次数据生成器（randomdigit）来得到 $a$。

输出格式

输出共有一行一个整数，为所有 $f(x)$ 的异或和。

3 0 12345678

175092810

114514 100000 1919810

212218651

9919810 2 12121121

204065242

提示

数据生成器

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

样例解释

序列 $a$ 为 $506005380,3857352168,531380003$。

$f(1),f(2),f(3)$ 模 $998244353$ 的值分别为 $506005380,370380136,39141030$。

数据范围

对于 $100\%$ 的数据，$0\le m\le 10^5,1\le n\le 10^7,0\le a_1,a_2,\cdots,a_n,seed<2^{32}$。

• Subtask $1$（$30\%$ 的数据）：$n\le 10^6,m\le 10^5$。

在此 Subtask 中：

有 $10\%$ 的数据，满足 $m=0$。

另有 $10\%$ 的数据，满足 $n\le 100$。

• Subtask $2$（剩下 $70\%$ 的数据）：$n\le 10^7,m\le 3$。

提示

请注意空间限制和常数因子对程序运行效率的影响