Background

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

Problem Description

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:

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, denoting $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, denoting the answers modulo $998244353$.

3 2
0 1

0 1 2

6 4
11 43 27 7

0 88 176 1311 7332 53070

6 4
9 72 22 7

0 110 220 1551 8580 60990

Hint

Constraints

For $100\%$ of the testdata, $1 \le n, k \le 10^5$.

Translated by ChatGPT 5