Cho một số nguyên dương $N$ và một tập hợp các số nguyên $S = \{S_1, S_2, \dots, S_M\}$ có kích thước $M$.
Với mỗi $k = 0, 1, \dots, N - 3$, hãy trả lời câu hỏi sau:
Xét một đa giác đều $N$ cạnh có các đỉnh được đánh số $1, 2, \dots, N$. Vẽ đúng $k$ đường chéo sao cho không có hai đường chéo nào cắt nhau ngoại trừ có thể tại các đầu mút của chúng. Kết quả là đa giác đều $N$ cạnh được chia thành $k + 1$ đa giác. Gọi $e_1, e_2, \dots, e_{k+1}$ là số cạnh của các đa giác thu được này.
Ta nói một cách vẽ $k$ đường chéo là một cách tốt nếu nó thỏa mãn điều kiện sau:
- Tất cả $e_1, e_2, \dots, e_{k+1}$ đều nằm trong tập hợp $S$.
Hãy tính số cách tốt để vẽ $k$ đường chéo, chia lấy dư cho $998244353$.
Dữ liệu vào
Dữ liệu vào được cho dưới định dạng sau:
N M S1 S2 ... SM
- Tất cả các giá trị đầu vào đều là số nguyên.
- $3 \le N \le 10^5$
- $1 \le M \le N - 2$
- $3 \le S_i \le N$
- $S_i < S_{i+1}$
Kết quả
In ra $N - 2$ dòng. Với $i = 1, 2, \dots, N - 2$, in ra trên dòng thứ $i$ câu trả lời tương ứng với $k = i - 1$.
Ví dụ
Dữ liệu vào mẫu 1
5 2 3 4
Kết quả mẫu 1
0 5 5
Dữ liệu vào mẫu 2
4 1 4
Kết quả mẫu 2
1 0
Dữ liệu vào mẫu 3
16 7 3 4 6 7 9 12 16
Kết quả mẫu 3
1 24 544 14280 120156 829464 3372120 10914816 24515700 40532624 52300160 42493880 17383860 2674440
Ghi chú
Trong ví dụ đầu tiên, khi $k = 0$, ta luôn có $e_1 = 5$. Vì $5$ không nằm trong $S$, nên câu trả lời là $0$.
Khi $k = 1$, ta luôn có $\{e_1, e_2\} = \{3, 4\}$, và cả hai giá trị này đều nằm trong $S$. Có $5$ cách để vẽ một đường chéo trong một ngũ giác đều, vì vậy câu trả lời là $5$.
Khi $k = 2$, ta luôn có $e_i = 3$ ($1 \le i \le 3$). Có $5$ cách để vẽ hai đường chéo không cắt nhau trong một ngũ giác đều, vì vậy câu trả lời là $5$.