AT_abc315_h [ABC315Ex] Typical Convolution Problem

题目描述

给定一个长为 $n$ 的序列 $a$，按如下方法计算 $f(x)$：

• $f(0)=1$;
• 当整数 $m\in[1,n]$ 时，$f(m)=a_m\times (\displaystyle\sum_{i+j\lt m} f(i)\times f(j))$。

对于每个整数 $i\in[1,n]$，计算 $f(i)$ $\bmod$ $998244353$ 的值。

输入格式

第一行为序列长度 $n$，第二行输入 $n$ 个整数表示序列 $a$。

输出格式

依次输出 $f(1)$，$f(2)$，…，$f(n)$ 对 $998244353$ 取模后的值，相邻两个数之间以单个空格隔开。

输入输出样例 #1

输入 #1

5
1 2 3 4 5

输出 #1

1 6 48 496 6240

输入输出样例 #2

输入 #2

3
12345 678901 2345678

输出 #2

12345 790834943 85679169

说明/提示

数据规模与约定

$1\le n\le 2\times 10^5$，$a_i\in[0,998244352]$。