問題文

長さ $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$ の順番によらないことが証明できます。

制約

• $1 \\leq N \\leq 1000$
• $1 \\leq K \\leq 10^{12}$
• $0 \\leq A_i \\leq 1000$
• 与えられる入力はすべて整数

入力

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

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

出力

答えを出力せよ。

入力例 1

2 2
10 30

出力例 1

40

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

入力例 2

4 10
0 0 0 0

出力例 2

0

入力例 3

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

出力例 3

236500026047