现在有若干种宝石，其中有 $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 0

output

0 0 2 4 8 12

explanation

以下的乘号可认为是旋转生成：

$$ 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$。

时间限制：$2\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例数据下载