【模板】分治 FFT

题目背景

也可用多项式求逆解决。

题目描述

给定长度为 $n-1$ 的数组 $g[1],g[2],..,g[n-1]$,求 $f[0],f[1],..,f[n-1]$,其中 $$f[i]=\sum_{j=1}^if[i-j]g[j]$$ 边界为 $f[0]=1$ 。答案模 $998244353$ 。

输入输出格式

输入格式


第一行一个正整数 $n$ 。 第二行共 $n-1$ 个非负整数 $g[1],g[2],..,g[n-1]$,用空格隔开。

输出格式


一行共 $n$ 个非负整数,表示 $f[0],f[1],..,f[n-1]$ 模 $998244353$ 的值。

输入输出样例

输入样例 #1

4
3 1 2

输出样例 #1

1 3 10 35

输入样例 #2

10
2 456 32 13524543 998244352 0 1231 634544 51

输出样例 #2

1 2 460 1864 13738095 55389979 617768468 234028967 673827961 708520894

说明

$2\leq n\leq 10^5$ $0\leq g[i]<998244353$