現在有若干種寶石，其中有 $a_k$ 種重量為 $k$。你想知道對於每個 $w\le n$，有多少種寶石串成的項鍊，使得項鍊上至少有 $2$ 個寶石，且相鄰的寶石均屬於不同種類，且這串寶石的總重量為 $w$。答案對 $998244353$ 取模。
注意：
- 項鍊的第一個寶石與最後一個寶石也應屬不同種類。
- 如果兩個方案可以透過旋轉或翻轉變成一致，也應當被認為是不同的方案。
輸入格式
第一行輸入一個正整數 $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
見下發文件。
範例輸出 2
見下發文件。
資料範圍
對於 $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$ |