A6757 | 「NOI2025」集合

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

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

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

小 X 想要知道所有特别的有序对的权值之和，请你帮助他求出这个值。由于答案可能较大，你只需要求出答案对 $998,244,353$ 取模后的结果。

从文件 set.in 中读入数据。

本题包含多组测试数据。

输入的第一行包含两个非负整数 $c, t$，分别表示测试点编号与测试数据组数。$c = 0$ 表示该测试点为样例。

接下来依次输入每组测试数据，对于每组测试数据：

第一行包含一个正整数 $n$，表示有 $2^n$ 个数。

第二行包含 $2^n$ 个非负整数 $a_0, \ldots, a_{2^n - 1}$。

输出到文件 set.out 中。

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