[ARC156D] Xor Sum 5

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

[problemUrl]: https://atcoder.jp/contests/arc156/tasks/arc156_d 長さ $ 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 $

答えを出力せよ。

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