Background

It can also be solved using polynomial inversion.

Problem Description

Given a sequence $g_{1\dots n - 1}$, find the sequence $f_{0\dots n - 1}$.

Here, $f_i=\sum_{j=1}^if_{i-j}g_j$, with the boundary condition $f_0=1$.

Take the answer modulo $998244353$.

Input Format

The first line contains an integer $n$.

The second line contains $n-1$ integers $g_{1\dots n - 1}$.

Output Format

Output one line with $n$ integers, representing the values of $f_{0\dots n - 1}$ modulo $998244353$.

4
3 1 2

1 3 10 35

10
2 456 32 13524543 998244352 0 1231 634544 51

1 2 460 1864 13738095 55389979 617768468 234028967 673827961 708520894

Hint

Constraints: $2\leq n\leq 10^5$, $0\leq g_i<998244353$.

Translated by ChatGPT 5