Description

Technic_Angel wants to use particles to create a beautiful crystal. Pathselector tells her that a crystal is made by combining $m$ clusters of particles. Each cluster has a beauty value (a non-negative integer less than $2^w$, where $w$ is a given positive integer), and the beauty value of a crystal is the XOR sum of the beauty values of all particles used to make it.

Technic_Angel has many particles: for each $i\in[0,2^w)\cap\Z$, she has exactly $v_i$ clusters of particles whose beauty value is $i$. Now Technic_Angel wants to know how many ways there are to make a crystal with beauty value $k$. (Two ways are different if and only if there exists a cluster of particles that is used in one way but not in the other; all particles are distinct.) Unfortunately, she cannot solve this problem, so she comes to you, who are good at OI.

After you finish this problem in $0.01\mu s$, the pleasantly surprised Technic_Angel wants you to solve the above problem for all $k\in[0,2^w)\cap\Z$. However, since the answer is too large, she only asks you to tell her the XOR sum of $((i+1)f(i))\bmod998244353$ for all $i$, where $f(i)$ is the number of ways to make a crystal with beauty value $i$. That is,

$$(f(0)\bmod P)\otimes(2f(1)\bmod P)\otimes\cdots\otimes(2^wf(2^w-1)\bmod P)$$

where $P=998244353$, and $\otimes$ denotes XOR. Note that this is the XOR of the values after taking modulo, not taking modulo after XOR.

Input Format

The first line contains two positive integers $m,w$, representing the number of particle clusters needed to form a crystal and the parameter in the problem.

The second line contains $2^w$ positive integers; the $i$-th integer represents $v_{i-1}$.

Output Format

Output one integer in one line, representing the XOR sum of $((i+1)f(i))\bmod 998244353$.

2 2
0 1 1 1

5

3 3
2 0 1 7 1 2 0 1

320

5 3
2 0 2 1 0 4 2 3

1482

Hint

Sample Explanation

Sample 1: Technic_Angel has three clusters of particles, with beauty values $1,2,3$. If we represent the beauty values of the selected particles as a sequence, then there is no way to form a crystal with beauty value $0$, and there is exactly one way each for beauty value $1$, $2$, and $3$ (they are $[2,3]$, $[1,3]$, and $[1,2]$, respectively). Therefore the answer is $0\otimes2\otimes3\otimes4=5$.

Constraints

Let $n=\sum v_i$. For all testdata, $0\le n,v_i<998244353$, $1\le m\le\min\{n,10^6\}$, $1\le w\le 20$.

Subtask	$n,m,w$	Special Properties	Score
1	$m=1$	$A$	5
2	$n\le200,w\le8$		10
3	$m=2$		20
4	None	$A,B$	25
5		$A$	38
6	$m\le 60000,w\le16$	None	2

Special property $A$: $n\le10^6$.

Special property $B$: $2^w\cdot m\le 6\cdot 10^7$.

Translated by ChatGPT 5