| Codeforces Round 459 (Div. 1) |
|---|
| Закончено |
Сознание Уилла связано с сознанием монстра с Обратной стороны, поэтому Уиллу известно все, о чем думает монстр. Неожиданно Уилл начал рисовать без остановок, страницу за страницей. Его мама Джойс и шериф Хоппер сложили все рисунки вместе и поняли, что это помеченное дерево!
Деревом называется связный ациклический граф. В дереве Уилла n вершин. Джойс и Хоппер не знают, что означает это дерево, поэтому они решили его исследовать, а также исследовать похожие деревья. Для каждого k такого, что 0 ≤ k ≤ n - 1, они собираются исследовать все такие помеченные деревья из n вершин, у которых ровно k ребер совпадают с ребрами дерева Уилла. Два помеченных дерева различны, если и только если существует пара вершин (v, u) такая, что в одном дереве существует ребро между вершинами v и u, а в другом — нет.
Хоппер и Джойс хотят узнать, сколько работы им предстоит, поэтому они просят вас посчитать для каждого k число помеченных деревьев из n вершин, у которых ровно k ребер совпадают с ребрами в дереве Уилла. Так как ответ может быть большим, выведите ответы по модулю 1000000007 = 109 + 7.
Первая строка содержит одно целое число n (2 ≤ n ≤ 100) — размер дерева.
Следующие n - 1 строк содержат ребра в дереве Уилла. Каждая строка содержит два целых числа v и u (1 ≤ v, u ≤ n, v ≠ u) — концы очередного ребра. Гарантируется, что заданный граф является деревом.
Выведите n целых чисел на одной строке. i-е из этих чисел должно быть равно числу помеченных деревьев из n вершин таких, что ровно i - 1 ребро совпадает с ребрами в дереве Уилла, по модулю 1000 000 007 = 109 + 7.
3
1 2
1 3
0 2 1
4
1 2
2 3
3 4
1 7 7 1
4
1 2
1 3
1 4
0 9 6 1
