Background

Enhanced version link

This is a template problem, with no background.

Problem Description

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

The coefficients of the polynomials are computed modulo $998244353$.

Input Format

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

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

Output Format

Output $n$ integers, representing the first $n$ coefficients of $B(x)$ in order: $b_0, b_1, ..., b_{n-1}$. Each coefficient should be the smallest non-negative integer modulo $998244353$.

9 18948465
1 2 3 4 5 6 7 8 9

1 37896930 597086012 720637306 161940419 360472177 560327751 446560856 524295016

4 1
1 1 0 0

1 1 0 0

4 2
1 1 0 0

1 2 1 0

4 3
1 1 0 0

1 3 3 1

Hint

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

Translated by ChatGPT 5