注意

この問題の実行時間制限は $10$ sec です。Writer解(C++)の実行時間は $2836$ ms です。

問題文

PCT 君は以下のような問題を考えました。

Repaint

数直線上にボールが置かれています。

座標 $i \, (i = 1, 2, \dots, N)$ には $A_i$ 個の赤いボールと $(2-A_i)$ 個の青いボールが置かれています。同じ座標に同じ色のボールがあったとしても区別します。

これら以外の場所にはボールは置かれていません。

長さ $(N-1)$ の順列 $p$ を $1$ つ選びます。そして、$1$ 以上 $(N-1)$ 以下の各整数 $i$ に対して以下の操作を行います。

• 座標 $(p_i+1)$ にあるボールを $1$ つ選ぶ。選んだボールの色を $X$ とする。

• 座標 $p_i$ にあるボールを $1$ 個選び、選んだボールの色を $X$ に塗り替える。

あり得る操作 $2^{2(N-1)} \times (N-1)!$ 通り全てに対して、操作後のボール $2N$ 個のうち赤いものの個数の総和を $\bmod 998244353$ で求めてください。

ただし、二つの操作が異なるとは、選んだ順列 $p$ が異なるか、操作の途中で選ぶいずれかのボールが異なることとします。

しかし、何者かによって $A_i$ の値が並び替えられてしまいました。そこで、問題を以下のように変更しました。

Swap and Repaint

$S=0,1,...,N$ に対して以下の問題を解いてください。

問題

$A$ の隣り合う $2$ 要素を選び入れ替えることを $S$ 回繰り返します。

$(N-1)^S$ 通り全ての並び替え方について、並び替えた後の $A$ に対して Repaint を解き、解の総和を $\bmod 998244353$ で求めてください。

入力

$N$
$A_1\ A_2\ \dots \ A_N$

• 入力は全て整数である。
• $2 \le N \le 10^5$
• $0 \le A_i \le 2$

出力

Swap and Repaint を解いてください。

出力は $N+1$ 行に渡ります。$i \, (1 \le i \le N+1)$ 行目には $S=i-1$ のときの解答を出力してください。

サンプル

3
0 1 2

132
228
420
804

5
0 1 2 0 1

27536
103424
406368
1615760
6446032
25739056

15
2 0 1 0 1 1 2 2 0 0 2 0 1 1 0

523214357
664692542
837880257
504621457
945832393
772710139
238318330
459847588
223465057
192424051
725446536
541034409
387888351
350563535
198609141
134414344