Polynomial Trigonometric Series Expansion

You are given a polynomial \(A(x) = a_0+a_1x+\cdots+a_{n-1}x^{n-1}\) (of degree at most \(n-1\)) and a function type indicator which is either sin or cos. Your task is to compute a polynomial \(F(x)\) modulo \(x^n\) under the modulus \(998244353\) such that:

\[ F(x)\equiv \begin{cases} \sin\,A(x)=\sum_{k\ge 0} (-1)^k\frac{A(x)^{2k+1}}{(2k+1)!} & \text{if type is sin}\\[8pt] \cos\,A(x)=\sum_{k\ge 0} (-1)^k\frac{A(x)^{2k}}{(2k)!} & \text{if type is cos} \end{cases} \pmod{\,x^n}. \]

Here, all operations including the computations of factorial inverses are performed modulo \(998244353\). Only terms with degree less than \(n\) are retained.

inputFormat

The input consists of two lines:

• The first line contains an integer \(n\) (the modulus for the polynomial truncation) and a string which is either sin or cos indicating the function to compute.
• The second line contains \(n\) space-separated integers \(a_0, a_1, \dots, a_{n-1}\) representing the coefficients of the polynomial \(A(x)\), where \(a_i\) is the coefficient for \(x^i\).

outputFormat

Output a single line containing \(n\) space-separated integers \(b_0, b_1, \dots, b_{n-1}\), representing the coefficients of the polynomial \(F(x)\) modulo \(998244353\).

sample

3 sin
0 1 0

0 1 0