Multiset's Subset's Product Sum Hard

問題文

長さが $N$ の整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。$k=1,2,...,N$ それぞれについて、以下の問題を解いてください。

問題

集合 $S=\{1,2,\ldots,N\}$ の要素数が $k$ の部分集合 $T=\{t_1,t_2,\ldots,t_k\}$ として考えられるもの全てに対して以下の値を求め、その総和を $998244353$ で割った余りを出力してください。

• $\prod_{i=1}^{k} A_{t_i}$

制約

• $1\leq N \leq 10^5$
• $-10^9 \leq A_i \leq 10^9$
• 入力は全て整数 　　

入力

入力は以下の形式で標準入力から与えられます。

出力

$N$ 個の整数を改行区切りで出力してください。ここで、 $i$ 番目の整数は $k=i$ の問題に対する答えとなります。

入力例1

2
3 5

出力例1

8
15

入力例2

3
2 -3 7

出力例2

6
998244340
998244311

入力例3

1
1000000000

出力例3

1755647