P7438 Easier Permutation Counting

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: $$ \sum\limits_{\pi} F(\text{cyc}_{\pi}) $$ where $\pi$ ranges over all permutations of length $m$ such that there is no position $i$ with $\pi_i = i$.

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 one line with $n$ integers, representing the answers modulo $998244353$.

### 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 | Subtask ID | Score | $n \leq$ | $k \leq$ | Other Constraints | | :----------: | :----------: | :----------: | :----------: | :----------: | | Subtask 1 | $1$ | $10$ | $6$ | | | Subtask 2 | $5$ | $2\times 10^3$ | $6$ | | | Subtask 3 | $6$ | $2\times 10^5$ | $1$ | | | Subtask 4 | $16$ | $2\times 10^5$ | $6$ | $F(x)=x^k$ | | Subtask 5 | $16$ | $2\times 10^5$ | $3$ | | | Subtask 6 | $56$ | $6\times 10^5$ | $100$ | | 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