Person in Charge

• SleepingCup

Problem Description

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

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

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

Little 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

This problem contains multiple test cases.

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

For each test case:

• 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, \ldots, a_{2^n - 1}$.

Output Format

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

Samples

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

117
2091

Sample 2

See set/set2.in and set/set2.ans in the contestant directory.

This sample satisfies the constraints of Test Case 2.

Sample 3

See set/set3.in and set/set3.ans in the contestant directory.

This sample satisfies the constraints of Test Case 3.

Sample 4

See set/set4.in and set/set4.ans in the contestant directory.

This sample satisfies the constraints of Test Case 9.

Data Range

For all test data, the following guarantees hold:

• $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: At most $24$ indices $i$ satisfy $a_i \neq 0$.
• Special Property B: For all $0 \le i < 2^n$, $a_i \neq 998,244,352$.