Цирк
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).