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$.

제한

힌트