נתון מספר שלם חיובי $N$ וקבוצת מספרים שלמים $S = \{S_1, S_2, \dots, S_M\}$ בגודל $M$.
עבור כל $k = 0, 1, \dots, N - 3$, ענו על השאלה הבאה.
נתבונן במצולע משוכלל בעל $N$ צלעות שקודקודיו מסומנים ב-$1, 2, \dots, N$. העבירו בדיוק $k$ אלכסונים כך שאף שני אלכסונים לא ייחתכו, פרט אולי בקצותיהם. כתוצאה מכך, המצולע המשוכלל בעל $N$ הצלעות מתחלק ל-$k + 1$ מצולעים. יהיו $e_1, e_2, \dots, e_{k+1}$ מספרי הצלעות של המצולעים המתקבלים.
נאמר שדרך להעביר $k$ אלכסונים היא דרך טובה אם היא מקיימת את התנאי הבא:
- כל הערכים $e_1, e_2, \dots, e_{k+1}$ מוכלים בקבוצה $S$.
חשבו את מספר הדרכים הטובות להעביר $k$ אלכסונים, מודולו $998244353$.
קלט
הקלט ניתן בפורמט הבא:
N M S1 S2 ... SM
- כל ערכי הקלט הם מספרים שלמים.
- $3 \le N \le 10^5$
- $1 \le M \le N - 2$
- $3 \le S_i \le N$
- $S_i < S_{i+1}$
פלט
הדפיסו $N - 2$ שורות. עבור $i = 1, 2, \dots, N - 2$, הדפיסו בשורה ה-$i$ את התשובה המתאימה ל-$k = i - 1$.
דוגמאות
קלט לדוגמה 1
5 2 3 4
פלט לדוגמה 1
0 5 5
קלט לדוגמה 2
4 1 4
פלט לדוגמה 2
1 0
קלט לדוגמה 3
16 7 3 4 6 7 9 12 16
פלט לדוגמה 3
1 24 544 14280 120156 829464 3372120 10914816 24515700 40532624 52300160 42493880 17383860 2674440
הערה
בדוגמה הראשונה, כאשר $k = 0$, תמיד מתקיים $e_1 = 5$. מאחר ש-$5$ אינו מוכל ב-$S$, התשובה היא $0$.
כאשר $k = 1$, תמיד מתקיים $\{e_1, e_2\} = \{3, 4\}$, ושני הערכים מוכלים ב-$S$. ישנן $5$ דרכים להעביר אלכסון אחד במחומש משוכלל, ולכן התשובה היא $5$.
כאשר $k = 2$, תמיד מתקיים $e_i = 3$ ($1 \le i \le 3$). ישנן $5$ דרכים להעביר שני אלכסונים שאינם נחתכים במחומש משוכלל, ולכן התשובה היא $5$.