Yet Another Tree Problem 3

정점 번호가 $1$번부터 $n$번까지 있는 트리를 생각하자. 트리는 $1$번 정점을 루트로 하는 루트 트리로 본다.

각 정점의 자식 수는 루트 $1$번 정점에서 멀어지는 방향으로 트리를 보았을 때, 그 정점의 바로 아래에 있는 정점의 개수이다.

양의 정수 $N,k$와 서로 다른 정수 $a_1,a_2,\cdots,a_k$가 주어진다. 모든 $n=1,2,\cdots,N$에 대해, 정점 번호가 $1$번부터 $n$번까지 있는 트리 중 모든 정점의 자식 수가 $a_1,a_2,\cdots,a_k$ 중 하나인 트리의 개수를 구하여라.

답이 매우 커질 수 있으므로, 각 답을 $998\ 244\ 353$으로 나눈 나머지로 출력한다.

입력은 다음과 같은 형식으로 주어진다.

$N\ k$ $a_1\ a_2\ \cdots\ a_k$

한 줄에 $N$개의 정수를 공백으로 구분하여 출력한다.

$i$번째 정수는 $n=i$일 때의 답을 $998\ 244\ 353$으로 나눈 나머지여야 한다.

• $1 \leq N \leq 200\ 000$.
• $2 \leq k \leq 1000$.
• $a_1=0$.
• $0 \leq a_i \leq 1000$ ($1 \leq i \leq k$).
• $a_i \neq a_j$ ($1 \leq i < j \leq k$).