Gefin er jákvæð heiltala $N$ og mengi heiltalna $S = \{S_1, S_2, \dots, S_M\}$ af stærð $M$.
Fyrir hvert $k = 0, 1, \dots, N - 3$ skaltu svara eftirfarandi spurningu.
Lítum á reglulegan $N$-hyrning þar sem hornpunktarnir eru merktir $1, 2, \dots, N$. Dragðu nákvæmlega $k$ hornalínur þannig að engar tvær hornalínur skerist nema hugsanlega í endapunktum sínum. Við þetta skiptist reglulegi $N$-hyrningurinn í $k + 1$ marghyrninga. Látum $e_1, e_2, \dots, e_{k+1}$ vera fjölda hliða í þessum marghyrningum sem myndast.
Við segjum að leið til að draga $k$ hornalínur sé góð leið ef hún uppfyllir eftirfarandi skilyrði:
- Öll gildin $e_1, e_2, \dots, e_{k+1}$ eru í menginu $S$.
Reiknaðu fjölda góðra leiða til að draga $k$ hornalínur, modulo $998244353$.
Inntak
Inntakið er gefið á eftirfarandi sniði:
N M S1 S2 ... SM
- Öll inntaksgildi eru heiltölur.
- $3 \le N \le 10^5$
- $1 \le M \le N - 2$
- $3 \le S_i \le N$
- $S_i < S_{i+1}$
Úttak
Prentaðu $N - 2$ línur. Fyrir $i = 1, 2, \dots, N - 2$, prentaðu á $i$-tu línu svarið sem samsvarar $k = i - 1$.
Dæmi
Dæmi um inntak 1
5 2 3 4
Dæmi um úttak 1
0 5 5
Dæmi um inntak 2
4 1 4
Dæmi um úttak 2
1 0
Dæmi um inntak 3
16 7 3 4 6 7 9 12 16
Dæmi um úttak 3
1 24 544 14280 120156 829464 3372120 10914816 24515700 40532624 52300160 42493880 17383860 2674440
Athugasemd
Í fyrsta dæminu, þegar $k = 0$, höfum við alltaf $e_1 = 5$. Þar sem $5$ er ekki í $S$ er svarið $0$.
Þegar $k = 1$ höfum við alltaf $\{e_1, e_2\} = \{3, 4\}$, og bæði gildin eru í $S$. Það eru $5$ leiðir til að draga eina hornalínu í reglulegum fimmhyrningi, svo svarið er $5$.
Þegar $k = 2$ höfum við alltaf $e_i = 3$ ($1 \le i \le 3$). Það eru $5$ leiðir til að draga tvær hornalínur sem skerast ekki í reglulegum fimmhyrningi, svo svarið er $5$.