31604번 - XOR Operations 다국어

You are given $n$ integers $a_1, a_2, \dots , a_n$. You have a sequence of $n$ integers $B = (b_1, b_2, \dots , b_n)$ which initially are all zeroes.

In one operation, you choose two different indices $i$ and $j$, then simultaneously

• replace $b_i$ with $b_i \oplus a_i \oplus a_j$, and
• replace $b_j$ with $b_j \oplus a_i \oplus a_j$.

Note that $\oplus$ represents the bitwise XOR operation, which returns an integer whose binary representation has a $1$ in each bit position for which the corresponding bits of either but not both operands are $1$. For example, $3 \oplus 10 = 9$ because $(0011)_2 \oplus (1010)_2 = (1001)_2$.

You want to compute the number of different possible sequences $B$ you can obtain after performing zero or more operations. Since this number might be huge, calculate this number modulo $998\, 244\, 353$.

Two sequences of length $n$ are considered different if and only if there exists an index $i$ ($1 ≤ i ≤ n$) such that the $i$-th element of one sequence differs from the $i$-th element of the other sequence.

The first line of input contains one integer $n$ ($2 ≤ n ≤ 200\, 000$). The second line contains $n$ integers $a_1, a_2, \dots , a_n$ ($0 ≤ a_i < 2^{30}$ for all $i$).

Output an integer representing the number of different possible sequences $B$ you can obtain after performing zero or more operations modulo $998\, 244\, 353$.