Problem Description

You are given an array of integers \( a \) of size \( n \). This array is non-decreasing, i.e., \( a_1 \leq a_2 \leq \ldots \leq a_n \).

You have to find arrays of integers \( b \) of size \( 2n-1 \), such that:

• \( b_{2i-1} = a_i \) (\( 1 \leq i \leq n \));
• array \( b \) is non-decreasing;
• \( b_1 \oplus b_2 \oplus \ldots \oplus b_{2n-1} = 0 \) (\( \oplus \) denotes bitwise XOR operation: https://en.wikipedia.org/wiki/Exclusive_or. In Kotlin, it is xor function).

Calculate the number of arrays that meet all the above conditions, modulo \( 998244353 \).

Input Format

The first line contains two integers \( n \) and \( 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 a single integer, the number of valid arrays \( b \) modulo \( 998244353 \).

Sample Input and Output

Sample Input #1

3 2
0 1 3

Sample Output #1

2

Sample Input #2

4 3
0 3 6 7

Sample Output #2

6

Sample Input #3

5 5
1 5 9 10 23

Sample Output #3

20

Sample Input #4

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

Sample Output #4

678132

见题面 Input 部分

见题面 Output 部分