P7620 CF1431J Zero-XOR Array

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

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$.

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 one line with one integer, the answer modulo $998244353$.

 Translated by ChatGPT 5