【模板】多项式快速幂

题目背景

[加强版传送门](https://www.luogu.com.cn/problem/P5273) (普通版与加强版的区别,仅有是否保证 $a_0=1$,以及 $k$ 的数据范围。) 模板题,无背景

题目描述

给定一个 $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\%$ 的数据:$1 < n \leq 10^5$,$2 \leq k \leq 10^{10^5}$,$a_i \in [0,998244352] \cap \mathbb{Z}$。