25738번 - 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. Roads are organized in a way such that no two pairs of roads connect the same pair of houses. In other words, the village can be treated as a simple graph where each house corresponds to vertices, and each road corresponds to edges. Note that 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$.

While the number of houses is not determined yet, you know that it will be an integer between 2ドル$ and $M$. You should calculate the sum of the scores for all possible villages with $N$ houses for each $N$ from 2ドル$ to $M$.

Since the answers can be large, output them modulo 998ドル,円 244,円 353$.

입력

The first line contains an 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 for all possible villages with $N$ houses, modulo 998ドル,円 244,円 353$. The answers should be separated by a space. 998ドル,円 244,円 353=119\times 2^{23}+1$ is a prime number.

제한

• 2ドル\leq M\leq 100,円 000$
• 0ドル\leq K\leq 3$
• 1ドル\leq A_i<998,円 244,円 353$ $(0\le i\le K)$

힌트