양의 정수 $N$과 크기가 $M$인 정수 집합 $S = \{S_1, S_2, \dots, S_M\}$이 주어집니다.
각 $k = 0, 1, \dots, N - 3$에 대해 다음 질문에 답하세요.
정점에 $1, 2, \dots, N$의 번호가 붙은 정$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$입니다.