Crystal Formation with XOR Beauty

Technic_Angel wants to create a beautiful crystal from particles. According to Pathselector, a crystal is composed of exactly \(m\) clusters (particles), each having a beauty value which is a non‐negative integer less than \(2^w\) (with \(w\) given). The beauty of the crystal is defined as the XOR (\(\oplus\)) of the beauty values of the chosen clusters.

Technic_Angel has many clusters. For every integer \(i\) with \(0\le i<2^w\), she has exactly \(v_i\) clusters of beauty \(i\). A valid way (scheme) to create a crystal is to choose exactly \(m\) clusters (all clusters are distinct, and two selections are considered different if there exists a cluster that is chosen in one selection and not the other). Let \(f(k)\) be the number of schemes to form a crystal with beauty \(k\) (i.e. the XOR of the \(m\) chosen clusters equals \(k\)).

Since there are too many values of \(k\) to output, Technic_Angel asks you to compute the following quantity:

[ \bigl((1\cdot f(0)\bmod P)\oplus(2\cdot f(1)\bmod P)\oplus\cdots\oplus(2^w\cdot f(2^w-1)\bmod P)\bigr), ]

where \(P=998244353\) and \(\oplus\) denotes the bitwise XOR operation. Note that the modulo is taken before the XOR!

Input Format: The input begins with two integers \(m\) and \(w\). Then a line follows containing \(2^w\) integers: \(v_0,v_1,\dots,v_{2^w-1}\), where \(v_i\) denotes the number of clusters available with beauty \(i\).

Output Format: Output a single integer which is the XOR of \((i+1)\cdot f(i) \bmod P\) for all \(0\le i<2^w\).

Note on Mathematics: Using \(X^i\) to denote the "shift" (here the effect on the XOR sum) and interpreting
\[ (1+z\cdot X^i)^{v_i} = \sum_{j=0}^{v_i} \binom{v_i}{j} z^j X^{(j \bmod 2)\cdot i}, \]
we see that for each type \(i\) the contribution depends only on whether an even or odd number of particles are chosen (since \(X^i\) squared gives the neutral element under XOR). In other words, for each \(i\) and choice number \(j\), if \(j\) is even then \(X\) is not affected while if \(j\) is odd then an \(i\) is contributed. The answer is obtained by extracting the coefficient of \(z^m\) in the product
\[ \prod_{i=0}^{2^w-1} \Bigl(\sum_{\substack{j=0\\j\;\text{even}}}^{v_i} \binom{v_i}{j} z^j + X^i \sum_{\substack{j=0\\j\;\text{odd}}}^{v_i} \binom{v_i}{j} z^j\Bigr), \]
and then combining the results with the given formula.

inputFormat

The first line contains two integers \(m\) and \(w\). The second line contains \(2^w\) integers \(v_0, v_1, \dots, v_{2^w-1}\), where \(v_i\) is the number of clusters with beauty \(i\).

outputFormat

Output a single integer: the XOR (\(\oplus\)) of \((i+1)\cdot f(i) \bmod 998244353\) for all \(0 \le i < 2^w\).

sample

1 2
1 1 1 1

4