Цирк#10315

Цирк

1 секунда

128 мегабайтів

Дуже складна

$n$ корів з цирку фермера Джона готуються до своїх майбутніх виступів. Усі дії відбуваються на дереві з вершинами, позначеними числами від $1$ до $n$ . "Початковий стан" визначається числом $k$ ( $1 \leq k \leq n$ 1 \le k \le n) і розміщенням корів $1, \dots, k$ 1, \ldots, k у вершинах дерева так, щоб жодні дві корови не знаходилися в одній вершині.

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

Для кожного $k$ ( $1 \leq k \leq n$ 1 \le k \le n) допоможіть коровам визначити кількість класів еквівалентності початкових станів: тобто максимальну кількість початкових станів, які вони можуть обрати, щоб жодні два не були еквівалентними. Оскільки ці числа можуть бути дуже великими, виведіть їх залишки по модулю $1 0^{9} + 7$ 10^9 + 7.

Вхідні дані

Рядок $1$ містить $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \le n \le 10^5).

Рядок $i$ ( $2 \leq i \leq n$ 2 \le i \le n) містить два цілі числа $a_{i}$ a_i і $b_{i}$ b_i, що позначають ребро між $a_{i}$ a_i і $b_{i}$ b_i у дереві.

Вихідні дані

Для кожного $i$ ( $1 \leq i \leq n$ 1 \le i \le n), у $i$ -му рядку виведіть відповідь для $k = i$ k = i по модулю $1 0^{9} + 7$ 10^9 + 7.

Приклади

Приклад 1

Приклад 2

Примітка

Для $k = 1$ k = 1 і $k = 2$ k = 2 будь-які два стани можуть бути перетворені один в одного. Тепер розглянемо $k = 3$ k = 3, і нехай $c_{i}$ c_i позначає місцезнаходження корови $i$ . Стан $(c_{1}, c_{2}, c_{3}) = (1, 2, 3)$ (c_1, c_2, c_3) = (1, 2, 3) еквівалентний станам $(1, 2, 5)$ (1, 2, 5) і $(1, 3, 2)$ (1, 3, 2). Однак не еквівалентний стану $(2, 1, 3)$ (2, 1, 3).