Xiao X has $2^n$ numbers, numbered from $0$ to $2^n - 1$, where the $i$-th number ($0 \le i < 2^n$) is $a_i$.

For $S \subseteq {0, 1, \dots, 2^n - 1}$, define $f(S)$ as the bitwise AND of all numbers in set $S$. Specifically, if $S$ is the empty set, then $f(S) = 2^n - 1$.

Define that an ordered pair $(P, Q)$ of subsets $P, Q$ of ${0, 1, \dots, 2^n - 1}$ (they can be empty) is special if and only if $P \cap Q = \varnothing$ and $f(P) = f(Q)$. The weight of an ordered pair $(P, Q)$ is the product of all numbers whose indices are contained in $P \cup Q$, that is, $\prod_{i \in P \cup Q} a_i$. Specifically, if $P \cup Q = \varnothing$, the weight of $(P, Q)$ is $1$.

Xiao X wants to know the sum of the weights of all special ordered pairs. Please help him compute this value. Since the answer may be large, you only need to output the result modulo $998,244,353$.

Input Format

Read from standard input.

This problem contains multiple test cases.

The first line of input contains two non-negative integers $c$ and $t$, representing the test point number and the number of test cases, respectively. $c = 0$ indicates that this test point is a sample.

Next, for each test case, input:

The first line contains a positive integer $n$, indicating there are $2^n$ numbers.

The second line contains $2^n$ non-negative integers $a_0, \dots, a_{2^n - 1}$.

Output Format

Output to standard output.

For each test case, output a single line containing one integer, which is the sum of the weights of all special ordered pairs, modulo $998,244,353$.

Sample

Input

0 2
2
1 2 3 4
3
1 1 1 1 1 1 1 1

Output

117
2091

Explanation

This sample contains two test cases.

For the first test case, the following are all special ordered pairs $(P, Q)$:

• $P = \varnothing$, $Q = \varnothing$, weight is $1$;
• $P = \varnothing$, $Q = {3}$, weight is $a_3 = 4$;
• $P = {3}$, $Q = \varnothing$, weight is $a_3 = 4$;
• $P = {0}$, $Q = {1, 2}$, weight is $a_0 \times a_1 \times a_2 = 6$;
• $P = {0}$, $Q = {1, 2, 3}$, weight is $a_0 \times a_1 \times a_2 \times a_3 = 24$;
• $P = {0, 3}$, $Q = {1, 2}$, weight is $a_0 \times a_1 \times a_2 \times a_3 = 24$;
• $P = {1, 2}$, $Q = {0}$, weight is $a_0 \times a_1 \times a_2 = 6$;
• $P = {1, 2, 3}$, $Q = {0}$, weight is $a_0 \times a_1 \times a_2 \times a_3 = 24$;
• $P = {1, 2}$, $Q = {0, 3}$, weight is $a_0 \times a_1 \times a_2 \times a_3 = 24$;

Thus the answer is $1 + 4 + 4 + 6 + 24 + 24 + 6 + 24 + 24 = 117$.

Second Sample

See ex_2.in and ex_2.ans in the download directory.

This sample meets the constraints of test point $2$.

Third Sample

See ex_3.in and ex_3.ans in the download directory.

This sample meets the constraints of test point $3$.

Fourth Sample

See ex_4.in and ex_4.ans in the download directory.

This sample meets the constraints of test point $9$.

Data Constraints

For all test data, it is guaranteed that:

• $1 \le t \le 3$;
• $2 \le n \le 20$;
• For all $0 \le i < 2^n$, $0 \le a_i < 998,244,353$.

Special property A: It is guaranteed that at most $24$ $i$ satisfy $a_i \ne 0$.

Special property B: It is guaranteed that for all $0 \le i < 2^n$, $a_i \ne 998,244,352$.