Background

This problem comes from Kotlin Heroes. However, submissions in other languages are allowed here.

Problem Description

You are given a sequence $a$ consisting of $n$ integers, where the $i$-th integer is $a_i$. The sequence is non-decreasing, i.e., $a_1 \le a_2 \le \ldots \le a_n$.

You need to find all sequences $b$ consisting of $2n-1$ integers such that all of the following conditions hold:

• $b_{2i−1}=a_i$ ($1\leq i\leq n$).

• $b$ is non-decreasing.

• $b1\oplus b2\oplus \ldots \oplus b_{2n−1}=0$ ($\oplus$ denotes the bitwise XOR operation. In Kotlin, it is represented by the function xor).

Compute the number of different sequences $b$ modulo $998244353$.

Input Format

The first line contains two integers $n, m$, indicating that $a_i, b_i < 2 ^ m$.

The second line contains $n$ integers $b_1, b_3,\ldots , b_{2n−1}$.

Output Format

Output one line with one integer, the answer modulo $998244353$.

3 2
0 1 3

2

4 3
0 3 6 7

6

5 5
1 5 9 10 23

20

10 7
39 62 64 79 81 83 96 109 120 122

678132

Hint

Translated by ChatGPT 5