Problem Description

Let $\text{cyc}_\pi$ denote the number of cycles into which the permutation $\pi$ of length $n$ can be decomposed when treated as a permutation. Given two integers $n$ and $k$, and a polynomial of degree $k-1$, for $1 \leq m \leq n$, compute:

$$ \sum\limits_{\pi} F(\text{cyc}_{\pi}) $$

where $\pi$ is a permutation of length $m$ such that there is no position $i$ where $\pi_i = i$.

Input Format

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

The second line contains $k$ integers, representing the coefficients of the polynomial from lowest to highest degree.

Output Format

A single line containing $n$ integers, representing the answers modulo $998244353$.

Sample Input and Output

Sample Input #1

3 2
0 1

Sample Output #1

0 1 2

Sample Input #2

6 4
11 43 27 7

Sample Output #2

0 88 176 1311 7332 53070

Sample Input #3

6 4
9 72 22 7

Sample Output #3

0 110 220 1551 8580 60990

Notes

Data Range

For $100\%$ of the data, $1 \leq n, k \leq 10^5$.

见题面 Input 部分

见题面 Output 部分