시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)21141083.333%

문제

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)$

예제 입력 1

4 0
2

예제 출력 1

2 8 64

예제 입력 2

5 1
3 4

예제 출력 2

7 327 96721 169832849

예제 입력 3

6 2
5 6 7

예제 출력 3

11 1566 3000672 306031599 466869291

예제 입력 4

7 3
8 9 10 11

예제 출력 4

17 5427 31856976 326774674 449014006 997476587