Problem Description

Technic_Angel wants to create a beautiful crystal using particles. Pathselector informs her that a crystal is synthesized from $m$ clusters of particles, each with 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 its particles.

Technic_Angel has many particles: for each $i \in [0, 2^w) \cap \mathbb{Z}$, she has exactly $v_i$ clusters of particles with beauty value $i$. Now, Technic_Angel wants to know how many ways there are to synthesize a crystal with beauty value $k$? (Two schemes are considered different if and only if there is a cluster of particles used in one scheme but not in the other; all particles are distinct.) Unfortunately, she doesn't know how to solve this problem, so she turns to you, an expert in OI.

After spending $0.01\mu s$ solving this problem, Technic_Angel is thrilled and wants you to solve the above problem for all $k \in [0, 2^w) \cap \mathbb{Z}$. However, since the answers are too large, she only asks you to tell her the XOR sum of $((i+1)f(i)) \bmod 998244353$ for all $i$, where $f(i)$ represents the number of ways to synthesize a crystal with beauty value $i$. That is,
$$ (f(0) \bmod P) \otimes (2f(1) \bmod P) \otimes \cdots \otimes (2^w f(2^w-1) \bmod P) $$
where $P = 998244353$ and $\otimes$ denotes XOR. Note that it is the XOR sum after modulo, not XOR followed by modulo.

Input Format

The first line contains two positive integers $m$ and $w$, representing the number of particles required to synthesize the crystal and the parameter in the problem, respectively.

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

Output Format

A single integer representing the XOR sum of $((i+1)f(i)) \bmod 998244353$.

Sample Input and Output

Sample Input #1

2 2
0 1 1 1

Sample Output #1

5

Sample Input #2

3 3
2 0 1 7 1 2 0 1

Sample Output #2

320

Sample Input #3

5 3
2 0 2 1 0 4 2 3

Sample Output #3

1482

Notes/Hints

Sample Explanation

Sample 1: Technic_Angel has three clusters of particles with beauty values $1, 2, 3$. Representing the beauty values of the selected particles as a sequence, there are no ways to synthesize a crystal with beauty value $0$, and there is one way each for beauty values $1, 2, 3$ (respectively $[2, 3]$, $[1, 3]$, and $[1, 2]$), so the answer is $0 \otimes 2 \otimes 3 \otimes 4 = 5$.

Data Range

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

Special Condition $A$: $n \le 10^6$.

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

见题面 Input 部分

见题面 Output 部分