Polynomial Multiplicative Inverse

Given a polynomial \( F(x) \) with coefficients modulo \( 998244353 \), find a polynomial \( G(x) \) such that \( F(x) \times G(x) \equiv 1 \pmod{x^n} \). In other words, if \( F(x)=\sum_{i=0}^{n-1} f_i x^i \) and \( G(x)=\sum_{i=0}^{n-1} g_i x^i \), then

\[ F(x) \times G(x) \equiv 1 \pmod{x^n}, \]

All arithmetic is performed modulo \( 998244353 \). You may assume that \( f_0 \) (the constant term of \( F(x) \)) is nonzero, so that the inverse polynomial exists.

inputFormat

The first line contains an integer \( n \) (\( 1 \leq n \leq N \), where \( N \) is the polynomial length for the inversion modulo \( x^n \)).

The second line contains \( n \) space-separated integers \( f_0, f_1, \dots, f_{n-1} \) representing the coefficients of \( F(x) \) in increasing order of power.

It is guaranteed that \( f_0 \) is nonzero modulo \( 998244353 \).

outputFormat

Output \( n \) space-separated integers \( g_0, g_1, \dots, g_{n-1} \) representing the coefficients of the polynomial \( G(x) \) such that \( F(x) \times G(x) \equiv 1 \pmod{x^n} \) modulo \( 998244353 \).

sample

3
1 0 0

1 0 0