Problem Description

Let $\text{cyc}_\pi$ be the number of cycles in the cycle decomposition when the permutation $\pi$ of length $n$ is viewed as a permutation (mapping). Given two integers $n, k$ and a polynomial of degree $k-1$, for each $1 \leq m \leq n$ compute:

where $\pi$ ranges over all permutations of length $m$ such that there is no position $i$ with $\pi_i = i$.

Input Format

The first line contains two integers $n$ and $k$.

The second line contains $k$ integers, giving the coefficients of the polynomial from low degree to high degree.

Output Format

Output one line with $n$ integers, representing the answers modulo $998244353$.

3 2
0 1

0 1 2

6 4
11 43 27 7

0 88 176 1311 7332 53070

Hint

Sample Explanation 1

Below are all permutations that satisfy the requirement when $m = 1, 2, 3$:

$\text{cyc}_{(2,1)} = 1, \text{cyc}_{(2,3,1)} = 1, \text{cyc}_{(3,1,2)} = 1$. So when $m = 1$ the answer is $0$, when $m = 2$ it is $1$, and when $m = 3$ it is $2$.

Constraints

For $100\%$ of the testdata, $1 \leq n \leq 6\times 10^5$, $1 \leq k \leq 100$, and $0 \leq [x^k]F(x) \leq 998244352$.

Translated by ChatGPT 5