#P18741. [正睿NOI2021训练] 第三题

[正睿NOI2021训练] 第三题

第三题

有 nn 个有标号的球、若干无标号的普通盒子,以及一个特殊盒子(饭盒)。所有使用的盒子都必须非空。

在一个普通盒子中放入任意正数个球,其权值总是 11;在特殊盒子中放入 c>0c>0 个球,其权值为给定的 fcf_c。一种放球方案的权值,是各个盒子权值的乘积。

对于每个 k=0,1,…,n−1k=0,1,\ldots,n-1,求把这 nn 个球放入恰好 kk 个普通盒子和一个特殊盒子的所有方案的权值之和,对 998244353998244353 取模。

特殊盒子可以区分;普通盒子之间不可区分,交换普通盒子的编号不会产生新方案。

输入格式

第一行一个正整数 nn;第二行 nn 个非负整数 f1,…,fnf_1,\ldots,f_n。

输出格式

一行 nn 个非负整数,依次对应 k=0,1,…,n−1k=0,1,\ldots,n-1 的答案。

数据范围

1≤n≤2×1051\le n\le2\times10^5,0≤fi<9982443530\le f_i<998244353。

样例 1

输入

3
1 1 1

输出

1 6 3

样例 2

输入

3
2 0 0

输出

0 6 6