XOR Sum of Divisor Convolution

Let \(a = [a_1, a_2, \dots, a_n]\) be a sequence of length \(n\) and \(m\) be a given constant. For any positive integer \(x\), define

\(f(x)=\sum_{d|x} \left(a_{\frac{x}{d}}\times \prod_{i=1}^{k_d} \binom{c_{d,i}+m}{m}\right)\) mod \(998244353\),

where every positive integer \(d\) has a standard prime factorization

\(d=\prod_{j=1}^{k_d}p_{d,j}^{c_{d,j}}\).

If you are not familiar with \(\binom{n}{m}\), it is defined as \(\dfrac{n!}{m!(n-m)!}\), where \(!\) denotes the factorial.

Your task is to compute \(f(1), f(2), \dots, f(n)\) and then output the bitwise XOR of all these \(f(x)\) values. (Note that each \(f(x)\) is computed modulo \(998244353\).)

inputFormat

The first line contains two integers \(n\) and \(m\) \( (1 \leq n \leq 10^5, 0 \leq m \leq 10^5)\) representing the length of the sequence and the constant \(m\) respectively.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) separated by spaces.

outputFormat

Output a single integer: the XOR of \(f(1), f(2), \dots, f(n)\), where each \(f(x)\) is computed modulo \(998244353\).

sample

3 1
1 2 3

0