29643번 - Поддеревья 다국어

문제

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

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

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

Наконец, вне зависимости от структуры дерева есть 2ドルn - 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$.

제한

힌트