#P17625. CF1431J Zero-XOR Array

CF1431J Zero-XOR Array

P7620 CF1431J Zero-XOR Array

题目描述

给定一个包含 nn 个整数的序列 aa,其中第 ii 个整数为 aia_i。这个序列满足单调不递减性质,即 a1≤a2≤…≤ana_1 \le a_2 \le \ldots \le a_n。

你需要找出所有包含 2n−12n-1 个整数的序列 bb,使其满足以下条件:

  • b2i−1=aib_{2i−1}=a_i (1≤i≤n1\leq i\leq n);

  • bb 满足单调不递减性质;

  • b1⊕b2⊕…⊕b2n−1=0b_1\oplus b_2\oplus \ldots \oplus b_{2n−1}=0(⊕\oplus 表示按位异或运算。在 Kotlin 语言中,用函数 xor 表示)。

请计算出不同的序列 bb 的个数对 998244353998244353 取模的结果。

输入格式

第一行两个整数 n,mn, m,表示 ai,bi<2ma_i, b_i < 2 ^ m。

第二行 nn 个整数 b1,b3,…,b2n−1b_1, b_3,\ldots , b_{2n−1}。

输出格式

输出一行,一个整数,表示答案对 998244353998244353 取模后的结果。

输入输出样例 #1

输入 #1

3 2
0 1 3

输出 #1

2

输入输出样例 #2

输入 #2

4 3
0 3 6 7

输出 #2

6

输入输出样例 #3

输入 #3

5 5
1 5 9 10 23

输出 #3

20

输入输出样例 #4

输入 #4

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

输出 #4

678132

说明/提示