시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB222100.000%

문제

Дерево --- это связный неориентированный граф без циклов. Поддеревом дерева $T$ называется его связный подграф.

В зависимости от структуры дерева у него может быть несколько поддеревьев. Например, у дерева-цепочки из $n$ вершин $n(n+1)/2$ поддеревьев, а у дерева-звезды ($n-1$ вершина связаны с одной центральной) количество поддеревьев равно $2^{n-1}+n-1$.

Аналогично может быть различное количество способов выделить в дереве два непересекающихся по вершинам поддерева, три непересекающихся поддерева, и т. д.

Наконец, вне зависимости от структуры дерева есть $2n - 1$ способ выбрать $n - 1$ непересекающееся поддерево и ровно один способ выбрать $n$ непересекающихся поддеревьев (просто $n$ изолированных вершин).

По заданному дереву с $n$ вершинами выведите для каждого $k$ от 1 до $n$ количество способов выбрать $k$ непересекающихся по вершинам поддеревьев данного дерева.

입력

Первая строка входного файла содержит $n$ ($2 \le n \le 100$). Следующие $n-1$ строка описывают ребра дерева.

출력

Выведите $n$ целых чисел: для каждого $k$ от 1 до $n$ выведите количество способов выбрать $k$ непересекающихся по вершинам поддеревьев заданного дерева. Выводите каждое число по модулю $10^9$.

예제 입력 1

5
1 2
2 3
3 4
4 5

예제 출력 1

15
35
28
9
1

예제 입력 2

5
1 2
1 3
1 4
1 5

예제 출력 2

20
38
28
9
1