Вам дано дерево с \(n\) вершинами. Напомним, что дерево — это связный неориентированный граф без циклов.
Пусть \(a_1, a_2, \ldots, a_n\) — последовательность целых чисел. Выполним следующую операцию ровно \(n\) раз:
- Выберем неудаленную вершину \(u\). Присвоим \(a_u :=\) количество неудаленных вершин, соседних с \(u\). Затем удалим вершину \(u\) вместе со всеми ребрами, концом которых она является.
Для каждого целого числа \(k\) от \(1\) до \(n\) найдите по модулю \(998\,244\,353\) количество различных последовательностей \(a_1, a_2, \ldots, a_n\), удовлетворяющих следующим условиям:
- можно получить \(a\), выполнив вышеупомянутую операцию ровно \(n\) раз в некотором порядке.
- \(\operatorname{gcd}(a_1, a_2, \ldots, a_n) = k\). Здесь \(\operatorname{gcd}\) означает наибольший общий делитель элементов в \(a\).
Выходные данные
Для каждого набора входных данных выведите в одной строке \(n\) целых чисел, где для каждого \(k\) от \(1\) до \(n\) \(k\)-е целое число обозначает ответ, когда \(\operatorname{gcd}\) равен \(k\).
Примечание
В первом наборе входных данных дерево изображено на рисунке.
- Если мы удалим вершины в порядке \(1 \rightarrow 2 \rightarrow 3\) или \(1 \rightarrow 3 \rightarrow 2\), то полученная последовательность будет \(a = [2, 0, 0]\), которая имеет \(\operatorname{gcd}\), равный \(2\).
- Если удалить узлы в порядке \(2 \rightarrow 1 \rightarrow 3\), то полученная последовательность будет \(a = [1, 1, 0]\), \(\operatorname{gcd}\) которой равен \(1\).
- Если удалить узлы в порядке \(3 \rightarrow 1 \rightarrow 2\), то полученная последовательность будет \(a = [1, 0, 1]\), \(\operatorname{gcd}\) которой равен \(1\).
- Если удалить узлы в порядке \(2 \rightarrow 3 \rightarrow 1\) или \(3 \rightarrow 2 \rightarrow 1\), то полученная последовательность будет \(a = [0, 1, 1]\), \(\operatorname{gcd}\) которой равен \(1\).
Обратите внимание, что здесь мы считаем количество различных последовательностей, а не количество различных порядков удаления узлов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3
2 1
1 3
2
1 2
|
3 1 0
2 0
|