P7440 "KrOI2021" Feux Follets

Note: $\sigma(5307)=7440$, and among all $x$ satisfying $\sigma(x)=7440$, this is the only number that is congruent to $7$ modulo $10$.

Let $\text{cyc}_\pi$ be the number of cycles in the permutation $\pi$ when $\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 \le m \le 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, denoting $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, denoting the answers modulo $998244353$.

### Constraints For $100\%$ of the testdata, $1 \le n, k \le 10^5$. Translated by ChatGPT 5