F. Плотности подмассивов
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть некоторое целое положительное число $$$c$$$. Будем называть массив $$$a_1, a_2, \ldots, a_n$$$ целых чисел $$$c$$$-массивом, если для всех $$$i$$$ выполнено $$$1 \leq a_i \leq c$$$. Будем называть $$$c$$$-массив $$$b_1, b_2, \ldots, b_k$$$ подмассивом $$$c$$$-массива $$$a_1, a_2, \ldots, a_n$$$, если существует такой набор из $$$k$$$ индексов $$$1 \leq i_1 < i_2 < \ldots < i_k \leq n$$$, такой, что $$$b_j = a_{i_j}$$$ для всех $$$1 \leq j \leq k$$$. Плотностью $$$c$$$-массива $$$a_1, a_2, \ldots, a_n$$$ будем называть максимальное целое неотрицательное число $$$p$$$, такое что любой $$$c$$$-массив, состоящий из $$$p$$$ чисел, будет являться подмассивом $$$a_1, a_2, \ldots, a_n$$$.

Вам дано число $$$c$$$ и некоторый $$$c$$$-массив $$$a_1, a_2, \ldots, a_n$$$. Найдите для всех $$$0 \leq p \leq n$$$ количество последовательностей индексов $$$1 \leq i_1 < i_2 < \ldots < i_k \leq n$$$ для $$$1 \leq k \leq n$$$, таких что плотность массива $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$ равна $$$p$$$. Так как эти количества могут получиться очень большими, найдите их по модулю $$$998\,244\,353$$$.

Входные данные

В первой строке находятся два целых числа $$$n$$$ и $$$c$$$, разделённых пробелами ($$$1 \leq n, c \leq 3\,000$$$). В следующей строке находятся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$, разделённых пробелами ($$$1 \leq a_i \leq c$$$).

Выходные данные

Выведите $$$n + 1$$$ число $$$s_0, s_1, \ldots, s_n$$$. Число $$$s_p$$$ должно равняться количеству последовательностей индексов $$$1 \leq i_1 < i_2 < \ldots < i_k \leq n$$$ для $$$1 \leq k \leq n$$$ по модулю $$$998\,244\,353$$$, таких что плотность массива $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$ равна $$$p$$$.

Примеры
Входные данные
4 1
1 1 1 1
Выходные данные
0 4 6 4 1
Входные данные
3 3
1 2 3
Выходные данные
6 1 0 0
Входные данные
5 2
1 2 1 2 1
Выходные данные
10 17 4 0 0 0
Примечание

В первом примере, заметим, что плотность массива будет всегда равна его длине. Существует $$$4$$$ последовательности индексов из одного индекса, $$$6$$$ из двух, $$$4$$$ из трех и $$$1$$$ из четырех.

Во втором примере, единственная последовательность индексов, такая что получится массив ненулевой плотности это все индексы, так как иначе будет не хватать хотя бы одного из чисел от $$$1$$$ до $$$3$$$ в массиве, а значит он не будет удовлетворять условию плотности для $$$p \geq 1$$$.