Background

Gokuhara Gonta is trying to learn FFT...

Problem Description

Given a non-negative integer sequence $a_0, a_1, \cdots, a_{2^n-1}$ of length $2^n$, compute the sequence $A = \text{DFT}^k(a)$.

Here, $\text{DFT}(b)_i$ is defined as:

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

Input Format

The first line contains two non-negative integers $n, k$.

The next line contains $2^n$ non-negative integers $a_0, a_1, \cdots, a_{2^n-1}$.

Output Format

Output one line with $2^n$ non-negative integers $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

Hint

Constraints

• Subtask 1 (10 pts): $n \le 11$ and $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): no additional constraints.

For all testdata, $1 \le n \le 17$, $1 \le k \le 10^{18}$, $0 \le a_i \le 998244353$.

Translated by ChatGPT 5