Score : $700$ points

Problem Statement

You are given a sequence of $N$ non-negative integers $A=(A_1,A_2,\dots,A_N)$ and a positive integer $K$.

Find the bitwise $\mathrm{XOR}$ of $\displaystyle \sum_{i=1}^{K} A_{X_i}$ over all $N^K$ sequences of $K$ positive integer sequences $X=(X_1,X_2,\dots,X_K)$ such that $1 \leq X_i \leq N\ (1\leq i \leq K)$.

Constraints

• $1 \leq N \leq 1000$
• $1 \leq K \leq 10^{12}$
• $0 \leq A_i \leq 1000$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $K$

$A_1$ $A_2$ $\dots$ $A_N$

Output

Print the answer.

2 2
10 30

40

There are four sequences to consider: $(X_1,X_2)=(1,1),(1,2),(2,1),(2,2)$, for which $A_{X_1}+A_{X_2}$ is $20,40,40,60$, respectively. Thus, the answer is $20 \oplus 40 \oplus 40 \oplus 60=40$.

4 10
0 0 0 0

0

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

236500026047