Du får gitt et positivt heltall $N$ og en mengde heltall $S = \{S_1, S_2, \dots, S_M\}$ av størrelse $M$.
For hver $k = 0, 1, \dots, N - 3$, svar på følgende spørsmål.
Betrakt en regulær $N$-kant der hjørnene er merket med $1, 2, \dots, N$. Trekk nøyaktig $k$ diagonaler slik at ingen to diagonaler krysser hverandre bortsett fra muligens i endepunktene. Som et resultat deles den regulære $N$-kanten inn i $k + 1$ polygoner. La $e_1, e_2, \dots, e_{k+1}$ være antall sider i disse resulterende polygonene.
Vi sier at en måte å trekke $k$ diagonaler på er en god måte hvis den oppfyller følgende betingelse:
- Alle $e_1, e_2, \dots, e_{k+1}$ er inneholdt i mengden $S$.
Beregn antall gode måter å trekke $k$ diagonaler på, modulo $998244353$.
Inndata
Inndataene er gitt på følgende format:
N M S1 S2 ... SM
- Alle inndataverdier er heltall.
- $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$ linjer. For $i = 1, 2, \dots, N - 2$, skriv ut på den $i$-te linjen svaret som tilsvarer $k = i - 1$.
Eksempler
Eksempelinndata 1
5 2 3 4
Eksempelutdata 1
0 5 5
Eksempelinndata 2
4 1 4
Eksempelutdata 2
1 0
Eksempelinndata 3
16 7 3 4 6 7 9 12 16
Eksempelutdata 3
1 24 544 14280 120156 829464 3372120 10914816 24515700 40532624 52300160 42493880 17383860 2674440
Merk
I det første eksempelet, når $k = 0$, har vi alltid $e_1 = 5$. Siden $5$ ikke er inneholdt i $S$, er svaret $0$.
Når $k = 1$, har vi alltid $\{e_1, e_2\} = \{3, 4\}$, og begge verdiene er inneholdt i $S$. Det er $5$ måter å trekke én diagonal på i en regulær femkant, så svaret er $5$.
Når $k = 2$, har vi alltid $e_i = 3$ ($1 \le i \le 3$). Det er $5$ måter å trekke to ikke-kryssende diagonaler på i en regulær femkant, så svaret er $5$.