题目描述

長さ $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}$ のビット単位 $\mathrm{XOR}$ を求めてください。

ビット単位 $\mathrm{XOR}$ 演算とは 非負整数 $A,\ B$ のビット単位 $\mathrm{XOR}$ 、$A\ \oplus\ B$ は、以下のように定義されます。

• $A\ \oplus\ B$ を二進表記した際の $2^k$ ($k\ \geq\ 0$) の位の数は、$A,\ B$ を二進表記した際の $2^k$ の位の数のうち一方のみが $1$ であれば $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$ の順番によらないことが証明できます。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを出力せよ。

题目大意

给定 $n$ 个数的数列 $a$ 和一个整数 $k$。 对于所有长度为 $k$，值域为 $[1,n]$ 的数列 $p$，求出 $\sum _{i=1}^{k} a_{p_i}$ 的异或和。

2 2
10 30

40

4 10
0 0 0 0

0

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$
• 与えられる入力はすべて整数

Sample Explanation 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$ となります。