Village Planning

As the mayor of the RUN town, you are planning to build a new village. The village consists of houses and roads connecting two different houses. No two roads connect the same pair of houses. In other words, the village can be treated as a simple graph, where each house is a vertex and each road is an edge. The village may be disconnected.

You want your village to be as simple as possible. Therefore, for any distinct houses $i$ and $j$, there should be at most $K$ simple paths from house $i$ to house $j$.

Let $N$ be the number of houses. The score of the village is $\prod_{1\le i<j\le N} A_{f(i,j)}$, where $f(i,j)$ is the number of simple paths from house $i$ to house $j$.

The number of houses is not yet determined, but it is an integer between $2$ and $M$. For each $N$ from $2$ to $M$, calculate the sum of the scores of all possible villages with $N$ houses.

Since the answers can be large, output them modulo $998244353$.

The first line contains two space-separated integers $M$ and $K$.

The second line contains $K+1$ space-separated integers $A_0, \dots, A_K$.

For each $N$ from $2$ to $M$, output the sum of the scores of all possible villages with $N$ houses, modulo $998244353$. The answers are separated by a space.

• $2\leq M\leq 100000$
• $0\leq K\leq 3$
• $1\leq A_i<998244353$ $(0\le i\le K)$