H. Сортировка подсчётом?
ограничение по времени на тест
8 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод
I want to end this life impulsively for the decisive time instead of living on the rails that have been laid out for me.
Kashii Moimi & Kaai Yuki, The Decisive Hour

Для массива $$$[b_1, b_2, \ldots, b_m]$$$, где $$$0 \le b_i \le m$$$, определим $$$f(b)$$$ как массив $$$[c_1, c_2, \ldots, c_m]$$$, такой что $$$c_i$$$ равно количеству вхождений числа $$$i$$$ в массиве $$$b$$$.

Определим значение $$$g(b)$$$ массива $$$[b_1, b_2, \ldots, b_m]$$$, где $$$0 \le b_i \le m$$$, следующим образом:

  • Изначально имеется пустое множество $$$S$$$. Создайте массив $$$d$$$, изначально равный массиву $$$b$$$.
  • Затем выполните следующую операцию $$$100^{100}$$$ раз: добавьте $$$d$$$ в $$$S$$$, после чего присвойте $$$d \gets f(d)$$$.
  • $$$g(b)$$$ — это количество различных массивов в $$$S$$$ после выполнения операций.

Теперь вам даны два целых числа $$$n$$$ и $$$k$$$, а также массив $$$[r_1, r_2, \ldots, r_n]$$$. Для каждого $$$1\le p\le k$$$ посчитайте количество массивов $$$[a_1, a_2, \ldots, a_n]$$$, где $$$0 \le a_i \le r_i$$$, таких что $$$g(a) = p$$$. Так как это число может быть большим, выведите его по модулю $$$998\,244\,353$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 50$$$, $$$1 \le k \le 1000$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$r_1, r_2, \ldots, r_n$$$ ($$$0 \le r_i \le n$$$).

Гарантируется, что сумма $$$n^3$$$ по всем наборам входных данных не превосходит $$$50^3$$$.

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

Для каждого набора входных данных выведите $$$k$$$ целых чисел — количество массивов $$$[a_1, a_2, \ldots, a_n]$$$ с $$$0 \le a_i \le r_i$$$, для которых $$$g(a) = 1, 2, \ldots, k$$$ соответственно.

Выводите ответы по модулю $$$998\,244\,353$$$.

Пример
Входные данные
6
2 5
2 2
5 6
4 5 1 4 5
7 7
7 6 5 5 6 7 6
11 7
5 8 9 10 11 4 10 11 7 8 11
12 7
12 12 12 12 12 12 12 12 12 12 12 12
5 10
0 0 0 0 1
Выходные данные
2 1 2 2 2 
2 4 14 60 554 395 
2 6 35 627 63856 171611 490235 
2 10 83 10495 286935908 71004446 630281080 
2 11 132 48996 207819517 474452948 13828302 
1 1 0 0 0 0 0 0 0 0
Примечание

В первом наборе входных данных $$$g([0, 0]) = g([1, 0]) = 1$$$, $$$g([0, 1]) = 2$$$, $$$g([2, 0]) = g([0, 2]) = 3$$$, $$$g([1, 1]) = g([2, 2]) = 4$$$, а $$$g([1, 2]) = g([2, 1]) = 5$$$.

Во втором наборе входных данных $$$f([4, 5, 1, 4, 5]) = [1, 0, 0, 2, 2]$$$, $$$f([1, 0, 0, 2, 2]) = [1, 2, 0, 0, 0]$$$, $$$f([1, 2, 0, 0, 0]) = [1, 1, 0, 0, 0]$$$, $$$f([1, 1, 0, 0, 0]) = [2, 0, 0, 0, 0]$$$, $$$f([2, 0, 0, 0, 0]) = [0, 1, 0, 0, 0]$$$, $$$f([0, 1, 0, 0, 0]) = [1, 0, 0, 0, 0]$$$, $$$f([1, 0, 0, 0, 0]) = [1, 0, 0, 0, 0]$$$. Поэтому $$$g([4, 5, 1, 4, 5]) = 7$$$.