题目描述

给定 $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$ 取模。

3
1 2 1

4

4
852415 852415 852415 852415

1

提示

样例解释 #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$。