题目背景

这是一道来自 Kotlin Heroes 的题目。但是这里允许其他语言提交。

题目描述

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;

• $b1\oplus b2\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$.

输入格式

第一行两个整数 $n, m$，表示 $a_i, b_i < 2 ^ m$。

第二行 $n$ 个整数 $b_1, b_3,\ldots , b_{2n−1}$。

输出格式

输出一行，一个整数，表示答案对 $998244353$ 取模后的结果。

题目大意

给定一个包含 $n$ 个整数的序列 $a$，其中第 $i$ 个整数为 $a_i$。这个序列满足单调不递减性质，即 $a_1 \le a_2 \le \ldots \le a_n$。

你需要找出所有包含 $2n-1$ 个整数的序列 $b$，使其满足以下条件：

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

• $b$ 满足单调不递减性质；

• $b1\oplus b2\oplus \ldots \oplus b_{2n−1}=0$（$\oplus$ 表示按位异或运算。在 Kotlin 语言中，用函数 xor 表示）。

请计算出不同的序列 $b$ 的个数对 $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

提示