Background

Gensokyo, the Spring Festival, and lights in every home.

Teacher Kamishirasawa Keine would of course not miss such a good chance... and assigned homework.

Problem Description

Now Cirno has homework for $T$ days. The homework for each day can be represented by an ordered pair $(n, V)$, where $n$ is the size of the set, and $V$ is a set of size $n$. Now Cirno needs to compute the sum of the XOR values over all subsets of $V$. The answer should be taken modulo $998\,244\,353$.

Formally:

$$\text{ans}\equiv \sum_{S \subseteq V} \mathop{\bigoplus}\limits_{ s \in S } s \pmod {998\,244\,353}$$

Input Format

The first line contains an integer $T$.

The following $T$ lines each contain an ordered pair $(n, V)$.

Output Format

Output $T$ lines, each containing one integer representing the answer.

1
3 1 2 3

12

Hint

• Subtask 1 (17 pts): $T, n \le 8$.
• Subtask 2 (22 pts): $T, n \le 100$.
• Subtask 3 (61 pts): $T, n \le 3\times 10^6$.

For $100\%$ of the testdata, $\sum |V| \le 3 \times 10^6, 0 \le p \le 10^9$.

Translated by ChatGPT 5