#P17934. Divide Polygon

Divide Polygon

Divide Polygon

给定正整数 NN 和含 MM 个整数的集合 S={S1,S2,…,SM}S=\{S_1,S_2,\ldots,S_M\}。

在顶点依次编号为 1,2,…,N1,2,\ldots,N 的正 NN 边形内,画出 kk 条不同的对角线,要求任意两条对角线除端点外不相交。它们将原多边形分成 k+1k+1 个多边形。

如果每个得到的多边形的边数都属于 SS,则这种画法合法。两个画法不同,当且仅当所选的对角线集合不同;顶点有编号,旋转或翻转不视为同一种画法。

对于每个 k=0,1,…,N−3k=0,1,\ldots,N-3,求合法画法数对 998244353998244353 取模的结果。

输入格式

N M
S_1 S_2 ... S_M

输出格式

输出 N−2N-2 行。第 ii 行回答 k=i−1k=i-1 时的答案。

数据范围

3≤N≤1053\le N\le10^5,1≤M≤N−21\le M\le N-2,3≤S1<S2<⋯<SM≤N3\le S_1<S_2<\cdots<S_M\le N。所有输入均为整数。

样例 1

输入:

5 2
3 4

输出:

0
5
5

样例 2

输入:

4 1
4

输出:

1
0

样例 3

输入:

16 7
3 4 6 7 9 12 16

输出:

1
24
544
14280
120156
829464
3372120
10914816
24515700
40532624
52300160
42493880
17383860
2674440