现在有若干种宝石，其中有 $a_k$ 种重量为 $k$。你想知道对于每个 $w\le n$，有多少种宝石串成的项链，使得项链上至少有 $2$ 个宝石，且相邻的宝石均属于不同种类，且这串宝石的总重量为 $w$。答案对 $998244353$ 取模。
注意：
- 项链的第一个宝石与最后一个宝石也应属不同种类。
- 如果两个方案可以通过旋转或翻转变成一致，也应当被认为是不同的方案。
输入格式
第一行输入一个正整数 $n$。
接下来输入一行 $n$ 个数，第 $k$ 个数表示 $a_k$。
输出格式
输出一行 $n + 1$ 个数，分别表示 $w=0,1,\dots n$ 时的方案数。
样例一
input
5
2 1 0 1 0output
0 0 2 4 8 12explanation
以下的乘号可认为是旋转生成：
$$ 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 $$
样例二
见下发文件。
限制与约定
对于 $100\%$ 的数据，保证 $2 \le n\le 10^5, 0 \le a_i < 998244353$。
| 测试点编号 | $n$ | 特殊限制 |
|---|---|---|
| $1$ | $\le 8$ | |
| $2$ | $\le 50$ | |
| $3$ | $\le 10^5$ | 只存在重量为 $1$ 的宝石 |
| $4$ | $\le 3\times 10^2$ | |
| $5$ | ||
| $6$ | ||
| $7$ | $\le 3\times 10^3$ | |
| $8$ | ||
| $9$ | $\le 10^5$ | |
| $10$ |
时间限制：$2\texttt{s}$
空间限制：$512\texttt{MB}$