AT_arc222_e.XOR Matching

There are $N$ cards. The $i$-th card ($1\leq i\leq N$) has the integer $A_i$ written on it. Here, $0\leq A_i \leq 2^M-1$ holds.

For each integer $X=0,1,\ldots,2^M-1$, let $f(X)$ denote the answer to the following problem:

Consider forming some pairs of cards.

Each pair consists of two distinct cards, and the bitwise XOR of the integers written on those two cards must equal $X$. The same card cannot be included in multiple pairs.

Find the maximum number of pairs that can be formed under these conditions.

Output the following value:

\[ \left(\sum_{X=0}^{2M-1} f(X) \times 10 ^ X\right) \bmod 998244353 \]

What is the bitwise $\mathrm{XOR}$ operation

The bitwise $\mathrm{XOR}$ of non-negative integers $A, B$, $A \oplus B$, is defined as follows.

• The digit at the $2^k$ ($k \geq 0$) place of $A \oplus B$ in binary representation is $1$ if exactly one of the digits at the $2^k$ place of $A$ and $B$ in binary representation is $1$, and $0$ otherwise.

For example, $3 \oplus 5 = 6$ (in binary: $011 \oplus 101 = 110$).
In general, the bitwise $\mathrm{XOR}$ of $k$ non-negative integers $p_1, p_2, p_3, \dots, p_k$ is defined as $(\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$, and it can be proved that this does not depend on the order of $p_1, p_2, p_3, \dots, p_k$.

有 $N$ 张卡片。第 $i$ 张卡片（$1\leq i\leq N$）上写有一个整数 $A_i$。其中满足 $0\leq A_i \leq 2^M-1$。

对每个整数 $X=0,1,\ldots,2^M-1$，令 $f(X)$ 表示如下问题的答案：

考虑将若干张卡片两两配对。

每一对由两张互不相同的卡片组成，且这两张卡片上所写整数的按位异或（bitwise XOR）值必须恰好等于 $X$。同一张卡片不能出现在多个配对中。

在满足上述条件的前提下，求最多能形成多少对。

请输出以下值：

\[ \left(\sum_{X=0}^{2M-1} f(X) \times 10 ^ X\right) \bmod 998244353 \]

什么是按位 $\mathrm{XOR}$ 运算？

非负整数 $A, B$ 的按位 $\mathrm{XOR}$（记作 $A \oplus B$）定义如下：

• 在二进制表示下，$A \oplus B$ 的 $2^k$ 位（$k \geq 0$）上的数字为 $1$，当且仅当 $A$ 和 $B$ 在该位上的数字恰好有一个为 $1$；否则该位为 $0$。

例如，$3 \oplus 5 = 6$（二进制：$011 \oplus 101 = 110$）。
一般地，$k$ 个非负整数 $p_1, p_2, p_3, \dots, p_k$ 的按位 $\mathrm{XOR}$ 定义为 $(\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$，并且可以证明该结果与 $p_1, p_2, p_3, \dots, p_k$ 的顺序无关。

The input is given from Standard Input in the following format:

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_N$

输入从标准输入给出，格式如下：

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_N$

Output the following value:

\[ \left(\sum_{X=0}^{2M-1} f(X) \times 10 ^ X\right) \bmod 998244353 \]

输出以下值：

\[ \left(\sum_{X=0}^{2M-1} f(X) \times 10 ^ X\right) \bmod 998244353 \]

Sample 1 Explanation:

• For $X=0$: two pairs $(A_1,A_2)$ and $(A_3,A_4)$ can be formed.
• For $X=1$: zero pairs can be formed.
• For $X=2$: two pairs $(A_1,A_4)$ and $(A_2,A_3)$ can be formed.
• For $X=3$: zero pairs can be formed.

Therefore, $f(0)=2$, $f(1)=0$, $f(2)=2$, and $f(3)=0$. The value to be output is $2\times 1 + 0\times 10 + 2\times 100 + 0\times 1000 = 202$.

Constraints

• $2\leq N\leq 2\times 10^5$
• $1\leq M\leq 20$
• $0\leq A_i \leq 2^M-1$ ($1\leq i\leq N$)
• All input values are integers.

样例 1 解释：

• 当 $X=0$ 时：可以形成两对 $(A_1,A_2)$ 和 $(A_3,A_4)$。
• 当 $X=1$ 时：无法形成任何对。
• 当 $X=2$ 时：可以形成两对 $(A_1,A_4)$ 和 $(A_2,A_3)$。
• 当 $X=3$ 时：无法形成任何对。

因此，$f(0)=2$，$f(1)=0$，$f(2)=2$，$f(3)=0$。需输出的值为 $2\times 1 + 0\times 10 + 2\times 100 + 0\times 1000 = 202$。

约束条件

• $2\leq N\leq 2\times 10^5$
• $1\leq M\leq 20$
• $0\leq A_i \leq 2^M-1$（其中 $1\leq i\leq N$）
• 所有输入值均为整数。