$N$ коров цирка Farmer John ($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$.

Входные данные

Строка $1$ содержит $N$.

Каждая из строк $2\le i\le N$ содержит два целых числа $a_i$ и $b_i$, обозначающих ребро между $a_i$ и $b_i$ в дереве.

Выходные данные

Для каждого $1\le i\le N,$ строка вывода с номером $i$ должна содержать ответ для $K=i$ по модулю $10^9+7$.

Примеры

Входные данные 1

5
1 2
2 3
3 4
3 5

Выходные данные 1

1
1
3
24
120

Примечание

При $K=1$ и $K=2,$ любые два состояния можно преобразовать друг в друга.

Теперь рассмотрим $K=3$ и обозначим через $c_i$ положение коровы $i$. Состояние $(c_1,c_2,c_3)=(1,2,3)$ эквивалентно состояниям $(1,2,5)$ и $(1,3,2).$ Однако оно не эквивалентно состоянию $(2,1,3).$

Входные данные 2

8
1 3
2 3
3 4
4 5
5 6
6 7
6 8

Выходные данные 2

1
1
1
6
30
180
5040
40320

Подзадачи

• В тестах 3–4 выполняется $N\le 8.$
• В тестах 5–7 выполняется $N\le 16.$
• В тестах 8–10 выполняется $N\le 100$, а дерево образует «звезду»: не более одной вершины имеет степень больше двух.
• В тестах 11–15 выполняется $N\le 100$.
• В тестах 16–20 нет дополнительных ограничений.

Автор задачи: Dhruv Rohatgi