Problem Description

Given a polynomial $A(x)$ of degree $n-1$, find a polynomial $F(x)$ modulo $x^n$ such that $F(x)\equiv\sin{A(x)}$ or $F(x)\equiv\cos{A(x)}$.

All operations are performed modulo $998244353$.

Input Format

The first line contains two integers $n,type$. If $type=0$, compute $\sin$; if $type=1$, compute $\cos$.

The second line contains $n$ integers, which are the coefficients $a_0,a_1,\cdots,a_{n-1}$ of the polynomial.

It is guaranteed that $a_0=0$.

Output Format

Output one line with $n$ integers, representing the coefficients $f_0,f_1,\cdots,f_{n-1}$ of the resulting polynomial.

8 0
0 4 2 6 1 5 3 7

0 4 2 332748113 998244338 931694687 998244320 72887640

8 1
0 4 2 6 1 5 3 7

1 0 998244345 998244345 665496220 332748123 44366450 133099314

Hint

Constraints for $100\%$ of the testdata: $n\leq10^5$, $a_i\in[0,998244352]\cap\mathbb{Z}$.

For the first $5$ test points, $type=0$; for the last $5$ test points, $type=1$.

Translated by ChatGPT 5