Mismatch

Time limit4sMemory limit512 MB

Summary

For each k from 1 to n, count the size-k subsequences whose bitwise AND is zero, modulo 998244353.

Level: Hard9 of 10
Topics: Bit manipulation, Combinatorics, Math
Solved: No attempts yet

Problem

You are given an array $a_1, a_2, \ldots, a_n$ of $n$ nonnegative integers. For each $k$ from $1$ to $n$ , find the number of subsequences of size $k$ ( $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$ ; $1 \le i_1 < \ldots < i_k \le n$ ) such that their bitwise AND is equal to zero ( $a_{i_1} \wedge a_{i_2} \wedge \ldots \wedge a_{i_k} = 0$ ). Since the answers can be very large, compute them modulo $998\,244\,353$ .

Two subsequences are considered distinct if there is an index $i$ such that the element $a_i$ is included in one of the subsequences but not the other.

Input

The first line contains an integer $n$ ( $1 \le n \le 2^{19}$ ). The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $0 \le a_i < 2^{19}$ ).

Output

Print $n$ space-separated integers $b_1, b_2, \ldots, b_n$ , where $b_i$ is the answer for $k = i$ modulo $998\,244\,353$ .

Examples2

Example 1
Input
```
3
0 1 2
```
Expected output
```
1 3 1
```
Example 2
Input
```
6
1 2 2 7 6 7
```
Expected output
```
0 3 9 10 5 1
```