В сети компании есть \(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\) целых чисел: \(k\)-е из них должно быть равно числу способов разбить компьютеры на \(k\) групп, соблюдая все описанные условия, по модулю \(998\,244\,353\).
Примечание
Ниже приведены все возможные разбиения компьютеров на \(4\) группы для второго примера:
- \(\{1, 2\}, \{3, 4\}, \{5\}, \{6, 7\}\);
- \(\{1\}, \{2\}, \{3, 4\}, \{5, 6, 7\}\);
- \(\{1, 2\}, \{3\}, \{4\}, \{5, 6, 7\}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
0 3 4 6
3 0 2 1
4 2 0 5
6 1 5 0
|
1 0 1 1
|
|
2
|
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
|