You are given a positive integer $N$ and a set of integers $S = \{S_1, S_2, \dots, S_M\}$ of size $M$.
For each $k = 0, 1, \dots, N - 3$, answer the following question:
Consider a regular $N$-gon whose vertices are labeled $1, 2, \dots, N$. Draw exactly $k$ diagonals so that no two diagonals intersect except possibly at their endpoints. As a result, the regular $N$-gon is divided into $k + 1$ polygons. Let $e_1, e_2, \dots, e_{k+1}$ be the numbers of sides of these resulting polygons.
We say that a way of drawing $k$ diagonals is a good way if it satisfies the following condition:
- All of $e_1, e_2, \dots, e_{k+1}$ are contained in the set $S$.
Compute the number of good ways to draw $k$ diagonals, modulo $998244353$.
Input
The input is given in the following format:
N M S1 S2 ... SM
- All input values are integers.
- $3 \le N \le 10^5$
- $1 \le M \le N - 2$
- $3 \le S_i \le N$
- $S_i < S_{i+1}$
Output
Output $N - 2$ lines. For $i = 1, 2, \dots, N - 2$, output on the $i$-th line the answer corresponding to $k = i - 1$.
Examples
Sample Input 1
5 2 3 4
Sample Output 1
0 5 5
Sample Input 2
4 1 4
Sample Output 2
1 0
Sample Input 3
16 7 3 4 6 7 9 12 16
Sample Output 3
1 24 544 14280 120156 829464 3372120 10914816 24515700 40532624 52300160 42493880 17383860 2674440
Note
In the first example, when $k = 0$, we always have $e_1 = 5$. Since $5$ is not contained in $S$, the answer is $0$.
When $k = 1$, we always have $\{e_1, e_2\} = \{3, 4\}$, and both values are contained in $S$. There are $5$ ways to draw one diagonal in a regular pentagon, so the answer is $5$.
When $k = 2$, we always have $e_i = 3$ ($1 \le i \le 3$). There are $5$ ways to draw two non-intersecting diagonals in a regular pentagon, so the answer is $5$.