[Cnoi2019] 数学作业

幻想乡，春节，万家灯火。 Kamishirasawa Keine 老师自然不会放过这么好的机会，，，布置作业。

现在 Cirno 手上有着 $T$ 天的作业，每天的作业可以用一个二元组 $( n, V )$ 表示，其中 $n$ 表示集合的大小， $V$ 表示大小为 $n$ 的集合. 现在，Cirno 需要求出的是 $V$ 的所有子集的异或和的和，答案对 $998\,244\,353$ 取模。 形式化地: $$ ans \equiv \sum_{S \subset V} \mathop{\oplus}\limits_{ p \in S } p \pmod {998\,244\,353} $$

第一行，一个整数 $T$。 以下 $T$ 行，每行一个二元组 $( n, V )$。

$T$ 行，每行一个整数，表示答案。

1
3 1 2 3

12

- Subtask 1（17pts）：$ T, n \le 8 $； - Subtask 2（22pts）：$ T, n \le 100 $； - Subtask 3（61pts）：$ T, n \le 3\times10^6 $。 对于 $100\%$ 的数据，$ \sum |V| \le 3 \times 10^6, 0 \le p \le 10^9$。