给定 $n$ 个整数 $a_1, a_2, \dots, a_n$。你有一个长度为 $n$ 的整数序列 $B = (b_1, b_2, \dots, b_n)$，初始时所有元素均为 0。

在一次操作中，你可以选择两个不同的下标 $i$ 和 $j$，然后同时执行：

• 将 $b_i$ 替换为 $b_i \oplus a_i \oplus a_j$，以及
• 将 $b_j$ 替换为 $b_j \oplus a_i \oplus a_j$。

注意 $\oplus$ 表示按位异或运算，即对于两个整数的二进制表示，若对应位上的值不同则结果为 1，相同则为 0。例如，$3 \oplus 10 = 9$，因为 $(0011)_2 \oplus (1010)_2 = (1001)_2$。

你需要计算在执行零次或多次操作后，可能得到的不同序列 $B$ 的数量。由于该数量可能非常大，请将其对 $998\,244\,353$ 取模。

若两个长度为 $n$ 的序列存在至少一个下标 $i$ ($1 \le i \le n$) 使得对应位置的元素不同，则认为这两个序列不同。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 200\,000$)。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i < 2^{30}$，对于所有 $i$)。

输出格式

输出一个整数，表示执行零次或多次操作后可能得到的不同序列 $B$ 的数量，对 $998\,244\,353$ 取模。

样例

输入 1

3
1 2 1

输出 1

4

说明 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。

输入 2

4
852415 852415 852415 852415

输出 2

1