RUN 마을의 시장으로서, 당신은 새로운 마을을 건설하려고 합니다. 마을은 집들과 서로 다른 두 집을 연결하는 양방향 도로로 구성됩니다. 도로는 어떤 두 집도 같은 도로로 두 번 연결되지 않도록 구성됩니다. 즉, 마을은 집을 정점으로, 도로를 양방향 간선으로 하는 단순 그래프로 간주할 수 있습니다. 마을은 연결되어 있지 않을 수도 있음에 유의하십시오.

당신은 마을을 가능한 한 단순하게 만들고 싶어 합니다. 따라서 서로 다른 임의의 두 집 $i$와 $j$에 대해, 집 $i$에서 집 $j$로 가는 단순 경로는 최대 $K$개여야 합니다.

$N$을 집의 개수라고 합시다. 마을의 점수는 다음과 같습니다.

$$\prod_{1 \le i < j \le N} A_{f(i, j)}$$

여기서 $f(i, j)$는 집 $i$에서 집 $j$로 가는 단순 경로의 개수입니다.

집의 개수는 아직 정해지지 않았지만, $2$에서 $M$ 사이의 정수라는 것을 알고 있습니다. 각 $N$ ($2 \le N \le M$)에 대하여, $N$개의 집을 가진 모든 가능한 마을의 점수 합을 계산해야 합니다. 답이 매우 클 수 있으므로, $998\,244\,353$으로 나눈 나머지를 출력하십시오.

입력

첫 번째 줄에는 두 개의 정수 $M$과 $K$가 공백으로 구분되어 주어집니다. 두 번째 줄에는 $K + 1$개의 정수 $A_0, \dots, A_K$가 공백으로 구분되어 주어집니다.

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

출력

$2$부터 $M$까지의 각 $N$에 대하여, $N$개의 집을 가진 모든 가능한 마을의 점수 합을 $998\,244\,353$으로 나눈 나머지를 출력하십시오. 각 답은 공백으로 구분되어야 합니다. $998\,244\,353 = 119 \cdot 2^{23} + 1$은 소수임에 유의하십시오.

예제

입력 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