Problem Description

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

All operations are performed under modulo \( 998244353 \).

Input Format

The first line contains two integers \( n \) and \( type \). If \( type = 0 \), it means to find \( \sin \); if \( type = 1 \), it means to find \( \cos \).

The second line contains \( n \) integers, representing the coefficients \( a_0, a_1, \cdots, a_{n-1} \) of the polynomial in order.

It is guaranteed that \( a_0 = 0 \).

Output Format

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

Sample Input and Output

Sample Input #1

8 0
0 4 2 6 1 5 3 7

Sample Output #1

0 4 2 332748113 998244338 931694687 998244320 72887640

Sample Input #2

8 1
0 4 2 6 1 5 3 7

Sample Output #2

1 0 998244345 998244345 665496220 332748123 44366450 133099314

Notes

For \( 100\% \) of the data: \( n \leq 10^5 \), \( a_i \in [0, 998244352] \cap \mathbb{Z} \).

The first 5 points have \( type = 0 \), and the last 5 points have \( type = 1 \).

见题面 Input 部分

见题面 Output 部分