JOHNKRAMは最近グラフ理論を研究しています。今日、彼は次のような問題に遭遇しました。多重辺や自己ループを持たない有向グラフが与えられます。このグラフの強連結成分を縮約して得られるグラフにおいて、入次数が $0$ である頂点の数はいくつでしょうか。

JOHNKRAMは Tarjan アルゴリズムを用いてこの問題を容易に解きました。しかし、彼よりもはるかに短いコードを書く人が多いことに気づき、そのプログラムを入手してみると、なんと常に $1$ を出力するプログラムでした。ランダムなデータは本当にこれほど単純なのでしょうか。そこで彼は多くの有向グラフをランダムに生成してみましたが、結果はすべて $1$ でした。そこで彼は生成方法を変更し、各強連結成分のサイズが特定の集合 $S$ に属するような有向グラフのみを生成するようにしたところ、答えはすぐに大きくなりました。

現在、JOHNKRAMはそれらの人々をすべて排除しましたが、データの強度を証明したいと考え、次のような問題を提起しました。頂点数 $i$ ($1 \leq i \leq n$) のラベル付き有向グラフのうち、すべての強連結成分のサイズが集合 $S$ に属するようなものについて、先ほどの問題の答えの期待値はいくらでしょうか。彼は自分では証明できないことに気づき、あなたに教えを請うことにしました。

入力

入力の1行目には、生成される有向グラフの最大頂点数を表す正整数 $n$ が含まれます。

続く $n$ 行のうち $i$ 行目には、整数 $s_i$ が含まれます。$s_i = 1$ の場合、$i$ は集合 $S$ に含まれ、$s_i = 0$ の場合、$i$ は集合 $S$ に含まれません。

出力

合計 $n$ 行を出力してください。各行には整数を1つ含めます。$i$ 行目の整数は、頂点数 $i$ ($1 \leq i \leq n$) のラベル付き有向グラフのうち、すべての強連結成分のサイズが集合 $S$ に属するものについて、先ほどの問題の答えの期待値を $mod\ 998244353$ で計算した結果です。条件を満たす有向グラフが存在しない場合は $0$ を出力してください。期待値が $a/b$ ($a$ と $b$ は互いに素な正整数) であるとき、出力する整数 $x$ は $bx \equiv a \pmod{998244353}$ かつ $0 \leq x < 998244353$ を満たす必要があります。

入出力例

入力 1

3
1
0
0

出力 1

1
332748119
519087065

注記

頂点数 $1$ の有向グラフにおいて、答えが $1$ となる有効なグラフは $1$ つであるため、期待値は $1$ であり、$mod\ 998244353$ で $1$ となります。

頂点数 $2$ の有向グラフにおいて、答えが $1$ となる有効なグラフは $2$ つ、答えが $2$ となる有効なグラフは $1$ つであるため、期待値は $\frac{4}{3}$ であり、$mod\ 998244353$ で $332748119$ となります。

頂点数 $3$ の有向グラフにおいて、答えが $1$ となる有効なグラフは $15$ つ、答えが $2$ となる有効なグラフは $9$ つ、答えが $3$ となる有効なグラフは $1$ つであるため、期待値は $\frac{36}{25}$ であり、$mod\ 998244353$ で $519087065$ となります。

制約

すべてのテストデータにおいて、$1 \leq n \leq 100000$、$0 \leq s_i \leq 1$ です。