Background

Link to the normal version.

This is a template problem with no background.

Problem Description

Given a degree $n-1$ polynomial $A(x)$, find a polynomial $B(x)$ under $\bmod\ x^n$ such that $B(x) \equiv (A(x))^k \ (\bmod\ x^n)$.

All polynomial coefficients are computed under $\bmod\ 998244353$.

Input Format

The first line contains two integers $n, k$.

The next line contains $n$ integers, which are the coefficients of $A(x)$ in order: $a_0, a_1, ..., a_{n-1}$.

Output Format

Output $n$ integers, which are the first $n$ coefficients of $B(x)$ in order: $b_0, b_1, ..., b_{n-1}$, each being the smallest non-negative integer modulo $998244353$.

2 2
1 1

1 2

Hint

For $100\%$ of the testdata, $1 < n \leq 10^5$, $0 \leq k \leq 10^{10^5}$, $a_i \in [0, 998244352]$.

Data update time.

Translated by ChatGPT 5