Ti vengono dati un intero positivo $N$ e un insieme di interi $S = \{S_1, S_2, \dots, S_M\}$ di dimensione $M$.
Per ogni $k = 0, 1, \dots, N - 3$, rispondi alla seguente domanda.
Considera un $N$-gono regolare i cui vertici sono etichettati con $1, 2, \dots, N$. Traccia esattamente $k$ diagonali in modo che nessuna coppia di diagonali si intersechi, tranne eventualmente nei loro estremi. Di conseguenza, l'$N$-gono regolare viene diviso in $k + 1$ poligoni. Siano $e_1, e_2, \dots, e_{k+1}$ i numeri di lati di questi poligoni risultanti.
Diciamo che un modo di tracciare $k$ diagonali è un buon modo se soddisfa la seguente condizione:
- Tutti i valori $e_1, e_2, \dots, e_{k+1}$ sono contenuti nell'insieme $S$.
Calcola il numero di buoni modi per tracciare $k$ diagonali, modulo $998244353$.
Input
L'input è fornito nel seguente formato:
N M S1 S2 ... SM
- Tutti i valori di input sono interi.
- $3 \le N \le 10^5$
- $1 \le M \le N - 2$
- $3 \le S_i \le N$
- $S_i < S_{i+1}$
Output
Stampa $N - 2$ righe. Per $i = 1, 2, \dots, N - 2$, stampa sulla $i$-esima riga la risposta corrispondente a $k = i - 1$.
Esempi
Input di esempio 1
5 2 3 4
Output di esempio 1
0 5 5
Input di esempio 2
4 1 4
Output di esempio 2
1 0
Input di esempio 3
16 7 3 4 6 7 9 12 16
Output di esempio 3
1 24 544 14280 120156 829464 3372120 10914816 24515700 40532624 52300160 42493880 17383860 2674440
Note
Nel primo esempio, quando $k = 0$, abbiamo sempre $e_1 = 5$. Poiché $5$ non è contenuto in $S$, la risposta è $0$.
Quando $k = 1$, abbiamo sempre $\{e_1, e_2\} = \{3, 4\}$, ed entrambi i valori sono contenuti in $S$. Ci sono $5$ modi per tracciare una diagonale in un pentagono regolare, quindi la risposta è $5$.
Quando $k = 2$, abbiamo sempre $e_i = 3$ ($1 \le i \le 3$). Ci sono $5$ modi per tracciare due diagonali che non si intersecano in un pentagono regolare, quindi la risposta è $5$.