题目背景

狱原权太正在尝试学习 FFT ……

题目描述

给定一个长度为 $2^n$ 的非负整数序列 $a_0,a_1,\cdots,a_{2^n-1}$，请计算序列 $A=\text{DFT}^k(a)$。

其中 $\text{DFT}(b)_i$ 定义为：

$$\text{DFT}(b)_i=\sum_{j=0}^{2^n-1}b_j\omega^{ij}\mod{998244353} $$$$\omega\equiv3^{\frac{998244352}{2^n}}\pmod{998244353} $$

输入格式

第一行两个非负整数 $n,k$。

接下来一行 $2^n$ 个非负整数 $a_0,a_1,\cdots,a_{2^n-1}$。

输出格式

一行 $2^n$ 个非负整数 $A_0,A_1,\cdots,A_{2^n-1}$。

3 3
1 2 3 4 5 6 7 8

288 831546728 224054051 383438562 998244321 614805727 774190238 166697561

提示

数据规模与约定

• Subtask 1（10 pts）：$n\le 11$ 且 $k\le 10$；
• Subtask 2（10 pts）：$k\le 10$；
• Subtask 3（20 pts）：$n\le 5$；
• Subtask 4（30 pts）：$n\le 11$；
• Subtask 5（30 pts）：无额外限制。

对于所有数据，$1\le n\le 17$，$1\le k\le10^{18}$，$0\le a_i\le 998244353$。