正の整数 $N$ と、要素数 $M$ の整数の集合 $S = \{S_1, S_2, \dots, S_M\}$ が与えられます。
各 $k = 0, 1, \dots, N - 3$ について、次の質問に答えてください。
頂点に $1, 2, \dots, N$ の番号が付いた正 $N$ 角形を考えます。どの二本の対角線も端点以外では交わらないように、ちょうど $k$ 本の対角線を引きます。その結果、正 $N$ 角形は $k + 1$ 個の多角形に分割されます。これらの多角形の辺の数を $e_1, e_2, \dots, e_{k+1}$ とします。
$k$ 本の対角線の引き方が次の条件を満たすとき、それを良い引き方と呼びます:
- $e_1, e_2, \dots, e_{k+1}$ がすべて集合 $S$ に含まれる。
$k$ 本の対角線の良い引き方の個数を $998244353$ で割った余りを求めてください。
入力
入力は以下の形式で与えられます:
N M S1 S2 ... SM
- 入力される値はすべて整数である。
- $3 \le N \le 10^5$
- $1 \le M \le N - 2$
- $3 \le S_i \le N$
- $S_i < S_{i+1}$
出力
$N - 2$ 行出力してください。$i = 1, 2, \dots, N - 2$ について、$i$ 行目に $k = i - 1$ に対応する答えを出力してください。
入出力例
入力例 1
5 2 3 4
出力例 1
0 5 5
入力例 2
4 1 4
出力例 2
1 0
入力例 3
16 7 3 4 6 7 9 12 16
出力例 3
1 24 544 14280 120156 829464 3372120 10914816 24515700 40532624 52300160 42493880 17383860 2674440
ノート
最初の例では、$k = 0$ のとき常に $e_1 = 5$ となります。$5$ は $S$ に含まれないため、答えは $0$ です。
$k = 1$ のとき常に $\{e_1, e_2\} = \{3, 4\}$ となり、どちらの値も $S$ に含まれます。正五角形に対角線を一本引く方法は $5$ 通りあるため、答えは $5$ です。
$k = 2$ のとき常に $e_i = 3$($1 \le i \le 3$)となります。正五角形に交わらない二本の対角線を引く方法は $5$ 通りあるため、答えは $5$ です。