n коров из цирка фермера Джона готовятся к своим грядущим выступлениям. Все действия происходят на дереве с вершинами, помеченными числами от 1 до n. "Начальное состояние" действия определяется числом k (1 ≤ k ≤ n) и назначением коров 1 .. k вершинам дерева так, чтобы никакие две коровы не находились в одной вершине.

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

Для каждого k (1 ≤ k ≤ n) помогите коровам определить количество классов эквивалентности начальных состояний: то есть максимальное количество начальных состояний, которые они могут выбрать, чтобы не было двух эквивалентных. Поскольку эти числа могут быть очень большими, выведите их остатки по модулю 109 + 7.

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

Строка 1 содержит n (1 ≤ n ≤ 105).

Строка i (2 ≤ i ≤ n) содержит два целых числа ai и bi обозначающих ребро между ai и bi в дереве.

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

Для каждого i (1 ≤ i ≤ n), в i - ой строке выведите ответ для k = i по модулю 109 + 7.

Пример 1

Для k = 1 и k = 2 любые два состояния могут быть преобразованы друг в друга. Теперь рассмотрим k = 3, и пусть ci обозначает местонахождение коровы i. Состояние (c1, c2, c3) = (1, 2, 3) эквивалентно состояниям ( 1, 2, 5) и (1, 3, 2). Однако не эквивалентно состоянию (2, 1, 3).