Problem Statement

Solve the following problem for $T$ test cases.

You are given an integer sequence $A$ of length $N$. Define $b_{i,j}$ as follows.

• $b_{1,j}:=A_j$　$(1 \le j \le N)$
• $b_{i,j}:=(b_{i-1,j}+b_{i-1,j+1})^2$　$(2 \le i \le N$ and $1 \le j \le N+1-i)$

Find $b_{N,1} \bmod 2^M$.

Input

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

Each case is given in the following format.

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_N$

• $1 \le T \le 2 \times 10^5$
• $1 \le N \le 2 \times 10^5$
• $1 \le M \le 30$
• $0 \le A_i < 2^M$
• The sum of $N$ over all cases does not exceed $2\times 10^5$.
• All input values are integers.

Output

Print $T$ lines. The $i$-th line should contain the answer for $\text{case}_i$.

Sample

3
3 4
3 3 4
2 30
10 10
7 5
31 25 6 28 14 29 22

9
400
17