問題文

$T$ 個のケースについて、以下の問題を解いてください。

長さ $N$ の整数列 $A$ が与えられます。 $b_{i,j}$ を以下で定義します。

• $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$ かつ $1 \le j \le N+1-i)$

$b_{N,1} \bmod 2^M$ を求めてください。

入力

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

各ケースは以下の形式で与えられる。

$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$
• すべてのケースについての $N$ の総和は $2\times 10^5$ を超えない。
• 入力はすべて整数

出力

$T$ 行出力せよ。 $i$ 行目には、 $\text{case}_i$ についての答えを出力せよ。

サンプル

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

9
400
17