典型卷积问题

题目描述

给你一个数列 $(A_1, A_2, \ldots , A_N)$。

我们按如下公式定义数列 $(F_0, F_1, \ldots , F_N)$。

$F_0 = 1$

$F_n = A_n\displaystyle\sum_{i+j\lt n}F_iF_j$ ($1 \le n \le N$)

求 $F_1, \ldots , F_N$ 对 $998244353$ 取模的值。

输入格式

输入按以下格式从标准输入给出。

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

输出格式

按顺序输出 $F_1, \ldots , F_N$ 对 $998244353$ 取模的值,用空格隔开。

样例

5
1 2 3 4 5

1 6 48 496 6240

$F_1 = A_1F_0F_0 = 1$。 $F_2 = A_2(F_0F_0+F_0F_1+F_1F_0) = 6$。 类似地,可得 $F_3 = 48, F_4 = 496, F_5 = 6240$。

3
12345 678901 2345678

12345 790834943 85679169

数据范围

• $1 \le N \le 2 \times 10^5$
• $0 \le A_i \lt 998244353$
• 输入中的所有值均为整数。