题目描述

小 X 有 $2^n$ 个数，编号为 $0$ 到 $2^n - 1$，第 $i$（$0 \leq i < 2^n$）个数为 $a_i$。

对于 $S \subseteq \{0, 1, \dots, 2^n - 1\}$，定义 $f(S)$ 为集合 $S$ 中所有数的二进制按位与；特别地，若 $S$ 为空集，则 $f(S) = 2^n - 1$。

定义两个 $\{0, 1, \dots, 2^n - 1\}$ 的子集 $P, Q$（可以为空）构成的有序对 $(P, Q)$ 是特别的，当且仅当 $P \cap Q = \emptyset$ 且 $f(P) = f(Q)$。定义有序对 $(P, Q)$ 的权值为编号包含在 $P \cup Q$ 内所有数的乘积，即 $\prod_{i \in P \cup Q} a_i$；特别地，若 $P \cup Q = \emptyset$，则有序对 $(P, Q)$ 的权值为 $1$。

小 X 需求出所有特别的有序对的权值之和，答案对 $998244353$ 取模。

输入格式

1. 第一行包含两个非负整数 $c, t$，分别表示测试点编号与测试数据组数，$c = 0$ 表示该测试点为样例。
2. 每组测试数据：
   • 第一行包含一个正整数 $n$，表示有 $2^n$ 个数。
   • 第二行包含 $2^n$ 个非负整数 $a_0, \dots, a_{2^n - 1}$。

输出格式

对于每组测试数据，输出一行一个整数，表示所有特别的有序对的权值之和对 $998244353$ 取模后的结果。

样例1

输入

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

输出

117
2091

样例1解释

该样例共包含两组测试数据：

1. 第一组测试数据（$n = 2$，$2^2 = 4$ 个数）： 所有特别的有序对 $(P, Q)$ 如下：
   • $P = \emptyset$，$Q = \emptyset$，权值为 $1$；
   • $P = \emptyset$，$Q = \{3\}$，权值为 $a_3 = 4$；
   • $P = \{3\}$，$Q = \emptyset$，权值为 $a_3 = 4$；
   • $P = \{0\}$，$Q = \{1, 2\}$，权值为 $a_0 \times a_1 \times a_2 = 6$；
   • $P = \{0\}$，$Q = \{1, 2, 3\}$，权值为 $a_0 \times a_1 \times a_2 \times a_3 = 24$；
   • $P = \{0, 3\}$，$Q = \{1, 2\}$，权值为 $a_0 \times a_1 \times a_2 \times a_3 = 24$；
   • $P = \{1, 2\}$，$Q = \{0\}$，权值为 $a_0 \times a_1 \times a_2 = 6$；
   • $P = \{1, 2, 3\}$，$Q = \{0\}$，权值为 $a_0 \times a_1 \times a_2 \times a_3 = 24$；
   • $P = \{1, 2\}$，$Q = \{0, 3\}$，权值为 $a_0 \times a_1 \times a_2 \times a_3 = 24$； 答案为 $1 + 4 + 4 + 6 + 24 + 24 + 6 + 24 + 24 = 117$。

数据范围

• 对于所有 $0 \leq i < 2^n$，均有 $0 \leq a_i < 998244353$。

特殊性质说明：

• A：保证至多存在 $24$ 个 $i$ 满足 $a_i \neq 0$。
• B：保证对于所有 $0 \leq i < 2^n$，均有 $a_i \neq 998244352$。