We have a tree with N vertices numbered 1 to N. The i-th edge in this tree connects Vertex a_i and b_i. For each k=1, ..., N, solve the problem below:

* Consider writing a number on each vertex in the tree in the following manner:
* First, write 1 on Vertex k.
* Then, for each of the numbers 2, ..., N in this order, write the number on the vertex chosen as follows:
* Choose a vertex that still does not have a number written on it and is adjacent to a vertex with a number already written on it. If there are multiple such vertices, choose one of them at random.
* Find the number of ways in which we can write the numbers on the vertices, modulo (10^9+7).

Constraints

* 2 \leq N \leq 2 \times 10^5
* 1 \leq a_i,b_i \leq N
* The given graph is a tree.

Input

Input is given from Standard Input in the following format:


N
a_1 b_1
:
a_{N-1} b_{N-1}


Output

For each k=1, 2, ..., N in this order, print a line containing the answer to the problem.

Examples

Input

3
1 2
1 3


Output

2
1
1


Input

2
1 2


Output

1
1


Input

5
1 2
2 3
3 4
3 5


Output

2
8
12
3
3


Input

8
1 2
2 3
3 4
3 5
3 6
6 7
6 8


Output

40
280
840
120
120
504
72
72
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
c=[[] for i in range(N)]
for a,b in AB:
    c[a-1].append(b-1)
    c[b-1].append(a-1)
v=[1]+[0]*(N-1)
x=[0]
s=[]
parent=[-1]*N
child=[[] for i in range(N)]
while x:
    p=x.pop()
    s.append(p)
    for n in c[p]:
        if v[n]==0:
            v[n]=1
            x.append(n)
            parent[n]=p
            child[p].append(n)
m=10**9+7
fac=[1]*(N+10)
inv=[1]*(N+10)
ifac=[1]*(N+10)
for n in range(2,N+10):
    fac[n]=(fac[n-1]*n)%m
    inv[n]=m-inv[m%n]*(m//n)%m
    ifac[n]=(ifac[n-1]*inv[n])%m
size=[1]*N+[0]
dp=[1]*N+[0]
for n in s[::-1]:
    p=parent[n]
    size[p]+=size[n]
    dp[n]=dp[n]*fac[size[n]-1]%m
    dp[p]=dp[p]*ifac[size[n]]*dp[n]%m
size2=[N-v+1 for v in size]
dp2=[1]*N
for n in s[1:]:
    p=parent[n]
    dp2[n]=dp[p]*ifac[size[p]-1]*dp2[p]*ifac[size2[p]-1]*pow(dp[n],m-2,m)*fac[size[n]]*fac[size2[n]-2]%m
for i in range(N):
    print(dp[i]*dp2[i]*fac[size[i]+size2[i]-2]*ifac[size[i]-1]*ifac[size2[i]-1]%m)