#52. 多项式乘方

题目类型:传统型 时间限制:5000 ms 空间限制:256 MiB
输入文件:标准输入 输出文件:标准输出 答案检查器:文本比较

这是一道模板题。

给定一个最高次数为 $n\ -\ 1$ 的多项式 $A(x)$ 和 $m$,求 $A(x)^m \bmod x^{n}$,对 $998244353$ 取模。


输入格式

第一行两个整数 $n$ 和 $m$。

第二行 $n$ 个整数,分别表示 $A(x)$ 的 $0$ 到 $n\ -\ 1$ 次项前的系数。

输出格式

一行 $n$ 个整数,分别表示乘起来后的多项式的 $0$ 到 $n\ -\ 1$ 次项前的系数。


样例一

Input

2 3
1 2

Output

1 6

Explanation

$(1\ +\ 2x)^3\ \equiv\ (1\ +\ 6x) \pmod{x^2}$


限制与约定

对于 $100\%$ 的数据,满足 $1\ \leq\ n\ \leq\ 200000,\ 1\ \leq\ m\ \leq\ 10^9$,保证输入中的系数大于等于 $0$ 且小于 $998244353$。

时间限制:$5\texttt{s}$

空间限制:$512\texttt{MB}$