Score : $675$ points

问题陈述

给定正整数 $N$, $M$, $K$，以及一个非负整数序列：$A=(A_1,A_2,\ldots,A_N)$。

对于一个非空非负整数序列 $B=(B_1,B_2,\ldots,B_{|B|})$，我们定义它的得分如下。

• 如果 $B$ 的长度是 $M$ 的倍数：$(B_1 \oplus B_2 \oplus \dots \oplus B_{|B|})^K$
• 否则：$0$

这里，$\oplus$ 表示按位异或。

找出 $A$ 的 $2^N-1$ 个非空子序列的得分之和，对 $998244353$ 取模。

什么是按位异或？非负整数 $A$ 和 $B$ 的按位异或，记作 $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, \dots, p_k$ 的异或定义为 $(\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k)$，可以证明这与 $p_1, \dots, p_k$ 的顺序无关。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given positive integers $N$, $M$, $K$, and a sequence of non-negative integers: $A=(A_1,A_2,\ldots,A_N)$.

For a non-empty non-negative integer sequence $B=(B_1,B_2,\ldots,B_{|B|})$, we define its score as follows.

• If the length of $B$ is a multiple of $M$: $(B_1 \oplus B_2 \oplus \dots \oplus B_{|B|})^K$
• Otherwise: $0$

Here, $\oplus$ represents the bitwise XOR.

Find the sum, modulo $998244353$, of the scores of the $2^N-1$ non-empty subsequences of $A$.

What is bitwise XOR? The bitwise XOR of non-negative integers $A$ and $B$, denoted as $A \oplus B$, is defined as follows:

• In the binary representation of $A \oplus B$, the digit at position $2^k$ ($k \geq 0$) is $1$ if exactly one of $A$ and $B$ has a $1$ in that position in their binary representations, and $0$ otherwise.

For example, $3 \oplus 5 = 6$ (in binary: $011 \oplus 101 = 110$).
In general, the XOR of $k$ integers $p_1, \dots, p_k$ is defined as $(\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k)$, and it can be proved that this is independent of the order of $p_1, \dots, p_k$.

Constraints

• $1 \leq N,K \leq 2 \times 10^5$
• $1 \leq M \leq 100$
• $0 \leq A_i < 2^{20}$
• All input values are integers.

Input

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

$N$ $M$ $K$

$A_1$ $A_2$ $\ldots$ $A_N$

Output

Print the answer.

Sample Input 1

3 2 2
1 2 3

Sample Output 1

14

Here are the scores of the $2^3-1=7$ non-empty subsequences of $A$.

• $(1)$: $0$
• $(2)$: $0$
• $(3)$: $0$
• $(1,2)$: $(1\oplus2)^2=9$
• $(1,3)$: $(1\oplus3)^2=4$
• $(2,3)$: $(2\oplus3)^2=1$
• $(1,2,3)$: $0$

Therefore, the sought sum is $0+0+0+9+4+1+0=14$.

Sample Input 2

10 5 3
100 100 100 100 100 100 100 100 100 100

Sample Output 2

252000000

Sample Input 3

16 4 100
7053 3876 3178 8422 7802 5998 2334 6757 6889 6637 7365 9495 7848 9026 7312 6558

Sample Output 3

432440016