异或 K 次方之和

题目描述

给定正整数 $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$ 的顺序无关。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出答案。

样例

3 2 2
1 2 3

14

以下是 $A$ 的 $2^3-1=7$ 个非空子序列的得分。

$(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$

因此所求之和为 $0+0+0+9+4+1+0=14$。

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

252000000

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

432440016

数据范围

• $1 \leq N,K \leq 2 \times 10^5$
• $1 \leq M \leq 100$
• $0 \leq A_i \lt 2^{20}$
• 所有输入值均为整数。