\(N\) коров из цирка Фермера Джона (\(1 \leq N \leq 10^5\)) готовят своё представление.
Оно будет происходить на дереве с вершинами помеченными \(1\ldots N\).
"Стартовое состояние" представления определяется числом \(1 \leq K \leq N\)
и назначением коров \(1\dots K\) вершинам на дереве так, что никакие две
коровы не размещаются в одной и той же вершине.
Во время представления коровы выполняют произвольно большое количество "шагов".
Во время "шага" корова перемещается из своей текущей вершины в соседнюю незанятую вершину.
Два стартовых состояния называются эквивалентными, если одно из них может быть
достигнуто из другого некоторой последовательностью шагов.
Для каждого \(1 \leq K \leq N\), помогите коровам определить количество
классов эквивалентности стартовых состояний: то есть максимальное количество
стартовых состояний, которое они могут выбрать, так что никакие два из них
не будут эквивалентными. Поскольку эти числа могут быть очень большими,
выведите их остатки по модулю \(10^9 + 7\).
ФОРМАТ ВВОДА (файл circus.in):
Строка
\(1\) содержит
\(N\).
каждая из строк \(2\le i\le N\) содержит да целых числа \(a_i\) и \(b_i\) обозначающих
ребро в дереве между вершинами \(a_i\) и \(b_i\).
ФОРМАТ ВЫВОДА (файл circus.out):
Для кажого \(1\le i\le N,\) \(i\)-ая строка вывода должна содержать ответ для
\(K=i\) по модулю \(10^9+7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2
2 3
3 4
3 5
|
1
1
3
24
120
|