P13626 [ICPC 2024 APC] XOR Operations

给定 $n$ 个整数 $a_1, a_2, \dots, a_n$。你有一个包含 $n$ 个整数的序列 $B=(b_1, b_2, \dots, b_n)$，初始时所有元素均为零。 在一次操作中，你选择两个不同的下标 $i$ 和 $j$，然后同时 * 将 $b_i$ 替换为 $b_i \oplus a_i \oplus a_j$，并且 * 将 $b_j$ 替换为 $b_j \oplus a_i \oplus a_j$。 注意，$\oplus$ 代表按位异或（bitwise XOR）操作。对于两个整数，其操作结果整数的每个二进制位，当且仅当两个操作数对应的二进制位有且仅有一个为 $1$ 时，该位为 $1$。例如，$3 \oplus 10 = 9$，因为 $(0011)_2 \oplus (1010)_2 = (1001)_2$。 你想要计算通过零次或多次操作可以得到的不同序列 $B$ 的数量。由于这个数字可能非常大，请计算结果对 $998,244,353$ 取模。 两个长度为 $n$ 的序列被认为是不同的，当且仅当存在一个下标 $i$ ($1 \le i \le n$)，使得一个序列的第 $i$ 个元素与另一个序列的第 $i$ 个元素不同。

输入的第一行包含一个整数 $n$ ($2 \le n \le 200,000$)。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i < 2^{30}$)。

输出一个整数，代表可以得到的不同序列 $B$ 的数量，结果对 $998,244,353$ 取模。

**样例解释 #1** 从 $B=(0,0,0)$ 开始，我们可以得到以下两个序列 $B$： * 对 $i=1$ 和 $j=2$ 执行操作。我们将得到 $B=(3,3,0)$。 * 在此之后，对 $i=2$ 和 $j=3$ 执行操作。我们将得到 $B=(3,0,3)$。 从 $B=(0,0,0)$ 开始，我们也可以得到以下序列 $B$： * 对 $i=2$ 和 $j=3$ 执行操作。我们将得到 $B=(0,3,3)$。 可以证明，$(0,0,0)$, $(3,3,0)$, $(3,0,3)$ 和 $(0,3,3)$ 是唯一可能得到的序列 $B$。因此，答案是 $4$。