【模板】多项式幂函数 (加强版)

题目背景

[普通版传送门](https://www.luogu.com.cn/problem/P5245) 模板题,无背景。 数据于 2020/3/10 更新并扩大 $m$ 的范围至最大值与普通版一致,此前提交的题解可能无法通过。 数据于 2020/8/6 二次更新,感谢 [hly1204](https://www.luogu.com.cn/user/242973)

题目描述

给定一个 $n-1$ 次多项式 $A(x)=\sum\limits_{i=0}^{n-1}a_i*x^i$,设多项式 $B(x)$ 满足 $B(x)=[A(x)]^m$,求 $B(x)$ 的前 $n$ 项系数。 多项式的系数在 $\mathrm{mod\:}\ 998244353$ 的意义下进行运算。

输入输出格式

输入格式


第一行两个整数 $n,m$ 接下来 $n$ 个整数,依次表示 $A(x)$ 的系数 $a_0, a_1,...,a_{n-1}$

输出格式


输出 $n$ 个整数,依次表示 $B(x)$ 的前 $n$ 项系数 $b_0, b_1,...,b_{n-1}$,要求 $0\leq b_i\leq 998244352$

输入输出样例

输入样例 #1

2 2
1 1

输出样例 #1

1 2

说明

对于 $100\%$ 的数据 $2\leq n \leq 10^5 $ ,$0 \leq a_i \leq 998244352 $ ,$0 \leq m \leq 10^{10^5}$