กำหนดจำนวนเต็มบวก $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$ ให้แสดงคำตอบที่สอดคล้องกับ $k = i - 1$ ในบรรทัดที่ $i$
ตัวอย่าง
ข้อมูลนำเข้าตัวอย่าง 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$