On vous donne un entier strictement positif $N$ et un ensemble d'entiers $S = \{S_1, S_2, \dots, S_M\}$ de taille $M$.
Pour chaque $k = 0, 1, \dots, N - 3$, répondez à la question suivante.
Considérez un $N$-gone régulier dont les sommets sont numérotés $1, 2, \dots, N$. Tracez exactement $k$ diagonales de sorte qu'aucune paire de diagonales ne s'intersecte, sauf éventuellement à leurs extrémités. Ainsi, le $N$-gone régulier est divisé en $k + 1$ polygones. Soient $e_1, e_2, \dots, e_{k+1}$ les nombres de côtés de ces polygones obtenus.
On dit qu'une façon de tracer $k$ diagonales est une bonne façon si elle vérifie la condition suivante :
- Tous les entiers $e_1, e_2, \dots, e_{k+1}$ appartiennent à l'ensemble $S$.
Calculez le nombre de bonnes façons de tracer $k$ diagonales, modulo $998244353$.
Entrée
L'entrée est donnée dans le format suivant :
N M S1 S2 ... SM
- Toutes les valeurs d'entrée sont des entiers.
- $3 \le N \le 10^5$
- $1 \le M \le N - 2$
- $3 \le S_i \le N$
- $S_i < S_{i+1}$
Sortie
Affichez $N - 2$ lignes. Pour $i = 1, 2, \dots, N - 2$, affichez sur la $i$-ième ligne la réponse correspondant à $k = i - 1$.
Exemples
Exemple d'entrée 1
5 2 3 4
Exemple de sortie 1
0 5 5
Exemple d'entrée 2
4 1 4
Exemple de sortie 2
1 0
Exemple d'entrée 3
16 7 3 4 6 7 9 12 16
Exemple de sortie 3
1 24 544 14280 120156 829464 3372120 10914816 24515700 40532624 52300160 42493880 17383860 2674440
Note
Dans le premier exemple, lorsque $k = 0$, on a toujours $e_1 = 5$. Comme $5$ n'appartient pas à $S$, la réponse est $0$.
Lorsque $k = 1$, on a toujours $\{e_1, e_2\} = \{3, 4\}$, et ces deux valeurs appartiennent à $S$. Il y a $5$ façons de tracer une diagonale dans un pentagone régulier, donc la réponse est $5$.
Lorsque $k = 2$, on a toujours $e_i = 3$ ($1 \le i \le 3$). Il y a $5$ façons de tracer deux diagonales ne s'intersectant pas dans un pentagone régulier, donc la réponse est $5$.