Yet Another Tree Problem 3

Consider a tree whose vertices are numbered from $1$ to $n$. The tree is regarded as a rooted tree with vertex $1$ as the root.

The number of children of a vertex is the number of vertices directly below it when the tree is viewed in the direction away from the root vertex $1$.

You are given positive integers $N,k$ and pairwise distinct integers $a_1,a_2,\cdots,a_k$. For every $n=1,2,\cdots,N$, count the number of trees on vertices $1,2,\cdots,n$ such that the number of children of every vertex is one of $a_1,a_2,\cdots,a_k$.

Since the answers can be very large, print each answer modulo $998\ 244\ 353$.

The input is given in the following format.

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

Print $N$ integers separated by spaces on one line.

The $i$-th integer must be the answer for $n=i$, modulo $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$).