5346: Convolution

Bob invented a new operation ⊗
Let p_i denote the i-th prime number. If x=∏_ip_i^ai and y=∏_ip_i^bi, then
x⊗y=∏_ip_i^{∣ai−bi∣}
Now Bob have a sequence a_1...n, he wants to calculate sequence b_1...n satisfies:
bi=∑_{1≤j,k≤n,j⊗k=i}a_jk^c
The answer may be very large, you only need to output:
(b₁mod998244353) xor (b₂mod998244353) ... xor (b_nmod998244353)
XOR means bitwise exclusive OR

The first line has two integers n,c.
The second line has n integers a_1...n.
1≤n≤10⁶
0≤a_i<998244353
0≤c≤10⁹

6 1
1 2 3 4 5 6

55