Цирк
n коров из цирка фермера Джона готовятся к своим грядущим выступлениям. Все действия происходят на дереве с вершинами, помеченными числами от 1 до n. "Начальное состояние" действия определяется числом k (1 ≤ k ≤ n) и назначением коров 1 .. k вершинам дерева так, чтобы никакие две коровы не находились в одной вершине.
В акте коровы совершают сколь угодно большое количество "ходов". Во время движения одна корова перемещается из своей текущей вершины в незанятую соседнюю вершину. Два начальных состояния называются эквивалентными, если одно из них может быть достигнуто из другого некоторой последовательностью ходов.
Для каждого k (1 ≤ k ≤ n) помогите коровам определить количество классов эквивалентности начальных состояний: то есть максимальное количество начальных состояний, которые они могут выбрать, чтобы не было двух эквивалентных. Поскольку эти числа могут быть очень большими, выведите их остатки по модулю 10^9 + 7.
Входные данные
Строка 1 содержит n (1 ≤ n ≤ 10^5).
Строка i (2 ≤ i ≤ n) содержит два целых числа a[i] и b[i] обозначающих ребро между a[i] и b[i] в дереве.
Выходные данные
Для каждого i (1 ≤ i ≤ n), в i - ой строке выведите ответ для k = i по модулю 10^9 + 7.
Пример 1
Для 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).