Se te da un entero positivo $N$ y un conjunto de enteros $S = \{S_1, S_2, \dots, S_M\}$ de tamaño $M$.
Para cada $k = 0, 1, \dots, N - 3$, responde a la siguiente pregunta.
Considera un $N$-ágono regular cuyos vértices están etiquetados como $1, 2, \dots, N$. Traza exactamente $k$ diagonales de modo que ningún par de diagonales se intersecte, salvo posiblemente en sus extremos. Como resultado, el $N$-ágono regular queda dividido en $k + 1$ polígonos. Sean $e_1, e_2, \dots, e_{k+1}$ los números de lados de estos polígonos resultantes.
Decimos que una forma de trazar $k$ diagonales es una buena forma si cumple la siguiente condición:
- Todos los valores $e_1, e_2, \dots, e_{k+1}$ están contenidos en el conjunto $S$.
Calcula el número de buenas formas de trazar $k$ diagonales, módulo $998244353$.
Entrada
La entrada se proporciona en el siguiente formato:
N M S1 S2 ... SM
- Todos los valores de entrada son enteros.
- $3 \le N \le 10^5$
- $1 \le M \le N - 2$
- $3 \le S_i \le N$
- $S_i < S_{i+1}$
Salida
Imprime $N - 2$ líneas. Para $i = 1, 2, \dots, N - 2$, imprime en la $i$-ésima línea la respuesta correspondiente a $k = i - 1$.
Ejemplos
Entrada de ejemplo 1
5 2 3 4
Salida de ejemplo 1
0 5 5
Entrada de ejemplo 2
4 1 4
Salida de ejemplo 2
1 0
Entrada de ejemplo 3
16 7 3 4 6 7 9 12 16
Salida de ejemplo 3
1 24 544 14280 120156 829464 3372120 10914816 24515700 40532624 52300160 42493880 17383860 2674440
Nota
En el primer ejemplo, cuando $k = 0$, siempre tenemos $e_1 = 5$. Como $5$ no está contenido en $S$, la respuesta es $0$.
Cuando $k = 1$, siempre tenemos $\{e_1, e_2\} = \{3, 4\}$, y ambos valores están contenidos en $S$. Hay $5$ formas de trazar una diagonal en un pentágono regular, por lo que la respuesta es $5$.
Cuando $k = 2$, siempre tenemos $e_i = 3$ ($1 \le i \le 3$). Hay $5$ formas de trazar dos diagonales que no se intersecten en un pentágono regular, por lo que la respuesta es $5$.