마을 계획

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$부터 $M$까지 바꿔 가며, 집이 $N$개인 가능한 모든 마을의 점수 합을 구하라.

답이 클 수 있으므로 $998244353$으로 나눈 나머지를 출력하라.

첫째 줄에 두 정수 $M$과 $K$가 공백으로 구분되어 주어진다.

둘째 줄에 공백으로 구분된 $K+1$개의 정수 $A_0, \dots, A_K$가 주어진다.

$2$부터 $M$까지의 각 $N$에 대해, 집이 $N$개인 가능한 모든 마을의 점수 합을 $998244353$으로 나눈 나머지를 출력한다. 답은 공백으로 구분한다.

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