• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

We have a city with $n$ apartments labeled with postal codes $1$ to $n$. The $i-$th road in this city, connects apartments $a_i$ and $b_i$. Consider delivering food orders to each apartment in the city in the following manner:

For each $k = 1, 2, ..., n$, Snapp Food wants to solve the following problem:

• First, deliver order $1$ to apartment $k$.
• Then, for each of the food orders $2, …, n$ in this sequence, deliver the order to the apartment chosen as follows: Choose an apartment that still does not have an order delivered to it and is adjacent to an apartment with an order already delivered to it. If there are multiple such apartments, choose one of them at random.

Find the number of ways in which we can deliver orders to the apartments, modulo $10^9 + 7$

input

The first line of the input is the number of apartments $n$. The following $n$ lines, each define a road from apartment $a_i$ to $b_i$.

$$2 \leq n \leq 200 000$$ $$1 \leq a_i, b_i\leq n$$

output

For each $k = 1, 2, ... , n$ in this sequence, print a line containing the answer to the problem.

example

sample input 1

3
1 2
1 3

sample output 1

2
1
1

sample input 2

5
1 2
2 3
3 4
3 5

sample output 2

2
8
12
3
3