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

В сети компании есть $$$n$$$ компьютеров. Они пронумерованы от $$$1$$$ до $$$n$$$.

Для каждой пары компьютеров $$$1 \leq i < j \leq n$$$ вы знаете значение $$$a_{i,j}$$$: сложность отправки сообщения между компьютерами $$$i$$$ и $$$j$$$. Значения $$$a_{i,j}$$$ для $$$i<j$$$ различны.

Вы хотите разделить компьютеры на $$$k$$$ множеств $$$A_1, A_2, \ldots, A_k$$$, чтобы следующие условия выполнялись:

  • для каждого компьютера $$$1 \leq i \leq n$$$ есть ровно одно множество $$$A_j$$$ такое, что $$$i \in A_j$$$;
  • для каждых двух пар компьютеров $$$(s, f)$$$ и $$$(x, y)$$$ ($$$s \neq f$$$, $$$x \neq y$$$) таких, что $$$s$$$, $$$f$$$, $$$x$$$ из одного множества, а $$$x$$$ и $$$y$$$ из разных, выполняется $$$a_{s,f} < a_{x,y}$$$.

Для каждого $$$1 \leq k \leq n$$$ найдите число способов разделить компьютеры на $$$k$$$ групп так, чтобы все упомянутые условия соблюдались. Эти значения могут быть большими, так что вам нужно найти их по модулю $$$998\,244\,353$$$.

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

В первой строке записано одно целое число $$$n$$$ ($$$1 \leq n \leq 1500$$$): количество компьютеров.

В $$$i$$$-й из следующих $$$n$$$ строк записаны $$$n$$$ целых чисел $$$a_{i,1}, a_{i,2}, \ldots, a_{i,n}$$$ ($$$0 \leq a_{i,j} \leq \frac{n (n-1)}{2}$$$).

Гарантируется, что:

  • для всех $$$1 \leq i \leq n$$$ выполняется $$$a_{i,i} = 0$$$;
  • для всех $$$1 \leq i < j \leq n$$$ выполняется $$$a_{i,j} > 0$$$;
  • для всех $$$1 \leq i < j \leq n$$$ выполняется $$$a_{i,j} = a_{j,i}$$$;
  • все $$$a_{i,j}$$$ для $$$i <j$$$ различны.
Выходные данные

Выведите $$$n$$$ целых чисел: $$$k$$$-е из них должно быть равно числу способов разбить компьютеры на $$$k$$$ групп, соблюдая все описанные условия, по модулю $$$998\,244\,353$$$.

Примеры
Входные данные
4
0 3 4 6
3 0 2 1
4 2 0 5
6 1 5 0
Выходные данные
1 0 1 1
Входные данные
7
0 1 18 15 19 12 21
1 0 16 13 17 20 14
18 16 0 2 7 10 9
15 13 2 0 6 8 11
19 17 7 6 0 4 5
12 20 10 8 4 0 3
21 14 9 11 5 3 0
Выходные данные
1 1 2 3 4 3 1
Примечание

Ниже приведены все возможные разбиения компьютеров на $$$4$$$ группы для второго примера:

  • $$$\{1, 2\}, \{3, 4\}, \{5\}, \{6, 7\}$$$;
  • $$$\{1\}, \{2\}, \{3, 4\}, \{5, 6, 7\}$$$;
  • $$$\{1, 2\}, \{3\}, \{4\}, \{5, 6, 7\}$$$.