Du får ett positivt heltal $N$ och en mängd heltal $S = \{S_1, S_2, \dots, S_M\}$ av storlek $M$.
För varje $k = 0, 1, \dots, N - 3$, besvara följande fråga.
Betrakta en regelbunden $N$-hörning vars hörn är numrerade $1, 2, \dots, N$. Dra exakt $k$ diagonaler så att inga två diagonaler skär varandra förutom möjligen i sina ändpunkter. Som ett resultat delas den regelbundna $N$-hörningen upp i $k + 1$ polygoner. Låt $e_1, e_2, \dots, e_{k+1}$ vara antalet sidor i dessa resulterande polygoner.
Vi säger att ett sätt att dra $k$ diagonaler är ett bra sätt om det uppfyller följande villkor:
- Alla $e_1, e_2, \dots, e_{k+1}$ ingår i mängden $S$.
Beräkna antalet bra sätt att dra $k$ diagonaler, modulo $998244353$.
Indata
Indatan ges i följande format:
N M S1 S2 ... SM
- Alla indatavärden är heltal.
- $3 \le N \le 10^5$
- $1 \le M \le N - 2$
- $3 \le S_i \le N$
- $S_i < S_{i+1}$
Utdata
Skriv ut $N - 2$ rader. För $i = 1, 2, \dots, N - 2$, skriv på den $i$-te raden ut svaret som motsvarar $k = i - 1$.
Exempel
Exempelindata 1
5 2 3 4
Exempelutdata 1
0 5 5
Exempelindata 2
4 1 4
Exempelutdata 2
1 0
Exempelindata 3
16 7 3 4 6 7 9 12 16
Exempelutdata 3
1 24 544 14280 120156 829464 3372120 10914816 24515700 40532624 52300160 42493880 17383860 2674440
Förklaring
I det första exemplet, när $k = 0$, har vi alltid $e_1 = 5$. Eftersom $5$ inte ingår i $S$ är svaret $0$.
När $k = 1$ har vi alltid $\{e_1, e_2\} = \{3, 4\}$, och båda värdena ingår i $S$. Det finns $5$ sätt att dra en diagonal i en regelbunden femhörning, så svaret är $5$.
När $k = 2$ har vi alltid $e_i = 3$ ($1 \le i \le 3$). Det finns $5$ sätt att dra två icke-skärande diagonaler i en regelbunden femhörning, så svaret är $5$.