The problem title is just to attract your attention~~~

JOHNKRAM has recently been studying graph theory. Today, he encountered the following problem: Given a directed graph with no multiple edges or self-loops, find the number of vertices with an in-degree of $0$ after condensing the graph into its strongly connected components (SCCs).

JOHNKRAM easily solved this problem using Tarjan's algorithm. However, he noticed that many others wrote much shorter code, so he requested their programs, only to find that they simply printed $1$. Could the random data really be that weak? He generated many random directed graphs and found that the answer was indeed always $1$. Consequently, he changed his generation method to only produce directed graphs where the size of every strongly connected component belongs to a specific set $S$. As a result, the answer immediately increased.

Now that JOHNKRAM has disqualified those people, he wants to prove the strength of the data. He poses the following question: For all labeled directed graphs with $i$ vertices ($1 \leq i \leq n$) where the size of every strongly connected component belongs to the set $S$, what is the expected value of the answer to the previous problem? He found he could not prove it, so he has come to ask for your help.

Input

The first line contains a positive integer $n$, representing the maximum number of vertices in the generated directed graphs.

The next $n$ lines each contain an integer $s_i$. If $s_i=1$, then $i$ is in the set $S$; otherwise, $i$ is not in the set $S$.

Output

Output $n$ lines, each containing an integer. The integer on the $i$-th line represents the expected value of the answer to the previous problem for all labeled directed graphs with $i$ vertices ($1 \leq i \leq n$) where the size of every strongly connected component belongs to the set $S$, modulo $998244353$. If no such valid directed graph exists, output $0$. If the expected value is $a/b$ (where $a$ and $b$ are coprime positive integers), you should output an integer $x$ such that $bx \equiv a \pmod{998244353}$ and $0 \leq x < 998244353$.

Examples

Input 1

3
1
0
0

Output 1

1
332748119
519087065

Note 1

For directed graphs with $1$ vertex, there is $1$ valid graph where the answer is $1$, so the expected value is $1$, which is $1 \pmod{998244353}$.

For directed graphs with $2$ vertices, there are $2$ valid graphs where the answer is $1$, and $1$ valid graph where the answer is $2$, so the expected value is $\frac{4}{3}$, which is $332748119 \pmod{998244353}$.

For directed graphs with $3$ vertices, there are $15$ valid graphs where the answer is $1$, $9$ valid graphs where the answer is $2$, and $1$ valid graph where the answer is $3$, so the expected value is $\frac{36}{25}$, which is $519087065 \pmod{998244353}$.

Constraints

For all test data, $1 \leq n \leq 100000$, $0 \leq s_i \leq 1$.