题目描述

给定一个长度为 $N$ 的非负整数序列 $A=(A_1,A_2,\dots,A_N)$，以及一个正整数 $K$。

满足 $1 \leq X_i \leq N\ (1\leq i \leq K)$ 的长度为 $K$ 的正整数序列 $X=(X_1,X_2,\dots,X_K)$ 一共有 $N^K$ 种。请你计算所有这些序列对应的 $\displaystyle\sum_{i=1}^{K} A_{X_i}$ 的按位异或（bitwise XOR）。

按位异或（bitwise XOR）运算定义如下：对于非负整数 $A,B$，$A \oplus B$ 表示 $A$ 和 $B$ 的二进制表示下，每一位 $2^k$（$k \geq 0$）的数，如果 $A,B$ 在该位上只有一个为 $1$，则结果为 $1$，否则为 $0$。

例如，$3 \oplus 5 = 6$（二进制表示为：$011 \oplus 101 = 110$）。 一般地，$k$ 个非负整数 $p_1,p_2,p_3,\dots,p_k$ 的按位异或为 $(\dots((p\_1 \oplus p\_2) \oplus p\_3)\oplus\dots\oplus p\_k)$，并且可以证明其结果与顺序无关。

输入格式

输入以如下格式从标准输入读入：

$N$ $K$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

输出答案。

样例 1

输入

2 2
10 30

输出

40

样例 2

输入

4 10
0 0 0 0

输出

0

样例 3

输入

11 998244353
314 159 265 358 979 323 846 264 338 327 950

输出

236500026047

说明/提示

限制条件

• $1 \leq N \leq 1000$
• $1 \leq K \leq 10^{12}$
• $0 \leq A_i \leq 1000$
• 所有输入均为整数

样例解释 1

$X$ 可能的取值为 $(X_1,X_2)=(1,1),(1,2),(2,1),(2,2)$ 共 $4$ 种，每种对应的 $A_{X_1}+A_{X_2}$ 分别为 $20,40,40,60$。因此答案为 $20 \oplus 40 \oplus 40 \oplus 60=40$。

由 ChatGPT 4.1 翻译