現在、数種類の宝石があり、そのうち重量が $k$ である宝石は $a_k$ 種類存在します。各 $w \le n$ について、以下の条件を満たす宝石を連ねたネックレスが何通りあるかを求めてください。答えは $998244353$ で割った余りを出力してください。

条件： - ネックレスには少なくとも $2$ 個の宝石が含まれる。 - 隣り合う宝石はすべて異なる種類である。 - ネックレスの総重量は $w$ である。

注意： - ネックレスの最初の宝石と最後の宝石も異なる種類である必要がある。 - 回転や反転によって一致する方案であっても、それらは異なる方案として扱う。

入力

一行目に正整数 $n$ が入力される。

続いて一行に $n$ 個の数値が入力され、$k$ 番目の数値は $a_k$ を表す。

出力

一行に $n + 1$ 個の数値を出力する。それぞれ $w=0, 1, \dots, n$ のときの方案数である。

入出力例

入力 1

5
2 1 0 1 0

出力 1

0 0 2 4 8 12

注記 1

以下の乗算は回転生成とみなすことができる：

$$ 2:[1,1']\times 2\\ 3:[1,2]\times 2,[1',2] \times 2\\ 4:[1,1',1,1'] \times 2,[1,1',2]\times 3,[1',1,2]\times 3\\ 5:[1,4]\times 2, [1',4]\times 2, [1,1',1,2]\times 4, [1',1,1',2]\times 4 $$

入力 2

配布ファイルを参照のこと。

制約

$100\%$ のデータにおいて、$2 \le n \le 10^5, 0 \le a_i < 998244353$ を満たす。