Дано целое положительное число $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$.