Gegeben sind eine positive ganze Zahl $N$ und eine Menge von ganzen Zahlen $S = \{S_1, S_2, \dots, S_M\}$ der Größe $M$.
Beantworte für jedes $k = 0, 1, \dots, N - 3$ die folgende Frage.
Betrachte ein regelmäßiges $N$-Eck, dessen Ecken mit $1, 2, \dots, N$ beschriftet sind. Zeichne genau $k$ Diagonalen ein, sodass sich keine zwei Diagonalen schneiden, außer möglicherweise in ihren Endpunkten. Dadurch wird das regelmäßige $N$-Eck in $k + 1$ Polygone unterteilt. Seien $e_1, e_2, \dots, e_{k+1}$ die Seitenanzahlen dieser entstehenden Polygone.
Wir nennen eine Möglichkeit, $k$ Diagonalen einzuzeichnen, eine gute Möglichkeit, wenn sie die folgende Bedingung erfüllt:
- Alle Werte $e_1, e_2, \dots, e_{k+1}$ sind in der Menge $S$ enthalten.
Berechne die Anzahl der guten Möglichkeiten, $k$ Diagonalen einzuzeichnen, modulo $998244353$.
Eingabe
Die Eingabe erfolgt im folgenden Format:
N M S1 S2 ... SM
- Alle Eingabewerte sind ganze Zahlen.
- $3 \le N \le 10^5$
- $1 \le M \le N - 2$
- $3 \le S_i \le N$
- $S_i < S_{i+1}$
Ausgabe
Gib $N - 2$ Zeilen aus. Gib für $i = 1, 2, \dots, N - 2$ in der $i$-ten Zeile die Antwort für $k = i - 1$ aus.
Beispiele
Beispieleingabe 1
5 2 3 4
Beispielausgabe 1
0 5 5
Beispieleingabe 2
4 1 4
Beispielausgabe 2
1 0
Beispieleingabe 3
16 7 3 4 6 7 9 12 16
Beispielausgabe 3
1 24 544 14280 120156 829464 3372120 10914816 24515700 40532624 52300160 42493880 17383860 2674440
Hinweis
Im ersten Beispiel gilt für $k = 0$ stets $e_1 = 5$. Da $5$ nicht in $S$ enthalten ist, lautet die Antwort $0$.
Für $k = 1$ gilt stets $\{e_1, e_2\} = \{3, 4\}$, und beide Werte sind in $S$ enthalten. Es gibt $5$ Möglichkeiten, eine Diagonale in ein regelmäßiges Fünfeck einzuzeichnen, also lautet die Antwort $5$.
Für $k = 2$ gilt stets $e_i = 3$ ($1 \le i \le 3$). Es gibt $5$ Möglichkeiten, zwei sich nicht schneidende Diagonalen in ein regelmäßiges Fünfeck einzuzeichnen, also lautet die Antwort $5$.