题目描述

YJC 希望能一举摧毁 \(W\) 国的军队，所以他决定动用核弹。\(C\) 国一共有 \(n\) 枚核弹头，编号为 \(1 \sim n\)，YJC 决定动用编号为 \(1 \sim i(1≤i≤n)\) 的核弹头。YJC 决定将核弹头分组，每一组选用一种可以正好装载这一组核弹头的导弹装载。对于每个 \(i(1≤i≤n)\)，\(C\) 国有 \(a_i\) 种可以装载正好 \(i\) 枚核弹头的导弹，每种导弹有无限多个。如果存在两枚核弹头在一种方案中被分在同一组，在另一种方案中没有被分在同一组，则这两种分组方案是不同的。如果两种装载方案的分组方案不同或分组方案相同但存在某一组核弹头选用的导弹不同，则这两种装载方案是不同的。现在 YJC 想知道，对于选用 \(i\) 枚核弹头，一共有多少种不同的装载方案。这个数字可能很大，你只需要输出它 \(\text{mod~998244353}\) 的值即可。

格式

输入格式

第一行包含一个整数 \(n\)，表示核弹头个数。
接下来 \(n\) 行，第 \((i+1)\) 行包含一个整数 \(a_i\)，表示装载正好i枚核弹头的导弹的种数。

输出格式

输出 \(n\) 行，第 \(i\) 行包含一个整数 \(d_i\)，表示选用 \(i\)枚核弹头不同的装载方案的种数。

样例1

样例输入1

3
1
1
1

样例输出1

1
2
5

样例解释

每种导弹都只有一种，所以装载方案数等于分组方案数。选用 \(1\) 枚核弹头时，分组方案只有 \(1\) 种{\((1)\)}。选用 \(2\) 枚核弹头时，分组方案有 \(2\) 种{\((1,2)\)}、{\((1),(2)\)}。选用 \(3\) 枚核弹头时，分组方案有 \(5\) 种{\((1,2,3)\)}、{\((1),(2,3)\)}、{\((1,2),(3)\)}、{\((1,3),(2)\)}、{\((1),(2),(3)\)}。

限制

\(30\%\) 的数据：\(n≤10\)。
\(100\%\) 的数据：\(1≤n≤3000，0≤ai<998244353\)。