給定一個正整數 $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$。