【模板】多项式快速幂

题目背景

模板题,无背景

题目描述

给定一个$n-1$次多项式$A(x)$,求一个在$\bmod\ x^n$意义下的多项式$B(x)$,使得$B(x) \equiv A^k(x) \ (\bmod\ x^n)$ 多项式的系数在$\bmod\ 998244353$的意义下进行运算。

输入输出格式

输入格式


第一行两个正整数$n,k$。 接下来$n$个整数,依次表示多项式的系数$a_0, a_1, \dots, a_{n-1}$ 保证$a_0 = 1$.

输出格式


输出$n$个整数,表示答案多项式的系数$b_0, b_1, \dots, b_{n-1}$

输入输出样例

输入样例 #1

9 18948465
1 2 3 4 5 6 7 8 9

输出样例 #1

1 37896930 597086012 720637306 161940419 360472177 560327751 446560856 524295016

输入样例 #2

4 1
1 1 0 0

输出样例 #2

1 1 0 0

输入样例 #3

4 2
1 1 0 0

输出样例 #3

1 2 1 0

输入样例 #4

4 3
1 1 0 0

输出样例 #4

1 3 3 1

说明

对于$100\%$的数据:$n \leq 10^5 \qquad 2 \leq k \leq 10^{10^5}\qquad a_i \in [0,998244352] \cap \mathbb{Z}$