Dana jest dodatnia liczba całkowita $N$ oraz zbiór liczb całkowitych $S = \{S_1, S_2, \dots, S_M\}$ o rozmiarze $M$.
Dla każdego $k = 0, 1, \dots, N - 3$ odpowiedz na następujące pytanie.
Rozważmy foremny $N$-kąt, którego wierzchołki są ponumerowane $1, 2, \dots, N$. Narysuj dokładnie $k$ przekątnych tak, aby żadne dwie przekątne nie przecinały się poza ewentualnie swoimi końcami. W rezultacie foremny $N$-kąt zostaje podzielony na $k + 1$ wielokątów. Niech $e_1, e_2, \dots, e_{k+1}$ oznaczają liczby boków otrzymanych wielokątów.
Mówimy, że sposób narysowania $k$ przekątnych jest dobrym sposobem, jeśli spełnia następujący warunek:
- Wszystkie liczby $e_1, e_2, \dots, e_{k+1}$ należą do zbioru $S$.
Oblicz liczbę dobrych sposobów narysowania $k$ przekątnych modulo $998244353$.
Wejście
Wejście jest podane w następującym formacie:
N M S1 S2 ... SM
- Wszystkie wartości wejściowe są liczbami całkowitymi.
- $3 \le N \le 10^5$
- $1 \le M \le N - 2$
- $3 \le S_i \le N$
- $S_i < S_{i+1}$
Wyjście
Wypisz $N - 2$ wierszy. Dla $i = 1, 2, \dots, N - 2$ wypisz w $i$-tym wierszu odpowiedź odpowiadającą wartości $k = i - 1$.
Przykłady
Przykładowe wejście 1
5 2 3 4
Przykładowe wyjście 1
0 5 5
Przykładowe wejście 2
4 1 4
Przykładowe wyjście 2
1 0
Przykładowe wejście 3
16 7 3 4 6 7 9 12 16
Przykładowe wyjście 3
1 24 544 14280 120156 829464 3372120 10914816 24515700 40532624 52300160 42493880 17383860 2674440
Uwaga
W pierwszym przykładzie dla $k = 0$ zawsze mamy $e_1 = 5$. Ponieważ $5$ nie należy do $S$, odpowiedź wynosi $0$.
Dla $k = 1$ zawsze mamy $\{e_1, e_2\} = \{3, 4\}$, a obie te wartości należą do $S$. Istnieje $5$ sposobów narysowania jednej przekątnej w pięciokącie foremnym, więc odpowiedź wynosi $5$.
Dla $k = 2$ zawsze mamy $e_i = 3$ ($1 \le i \le 3$). Istnieje $5$ sposobów narysowania dwóch nieprzecinających się przekątnych w pięciokącie foremnym, więc odpowiedź wynosi $5$.