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
import sys
input = sys.stdin.readline

N=int(input())
E=[[] for i in range(N+1)]

for i in range(N-1):
    a,b=map(int,input().split())
    E[a].append(b)
    E[b].append(a)

mod=10**9+7

FACT=[1]
for i in range(1,2*10**5+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**5,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0

TOP_SORT=[]
Q=[1]
P=[-1]*(N+1)
P[1]=0
P[0]=0

while Q:
    x=Q.pop()
    TOP_SORT.append(x)

    for to in E[x]:
        if P[to]==-1:
            P[to]=x
            Q.append(to)

Children=[1]*(N+1)
ANS_UP=[1]*(N+1)

for x in TOP_SORT[::-1]:
    sumchild=0
    for to in E[x]:
        if to==P[x]:
            continue
        sumchild+=Children[to]
        ANS_UP[x]=ANS_UP[x]*Combi(sumchild,Children[to])%mod
                    
    Children[P[x]]+=Children[x]
    ANS_UP[P[x]]=ANS_UP[P[x]]*ANS_UP[x]%mod

ANS_DOWN=[1]*(N+1)

for x in TOP_SORT:
    if x==1:
        continue
    ANS_DOWN[x]=ANS_DOWN[P[x]]*ANS_UP[P[x]]*Combi(N-Children[x]-1,N-Children[P[x]])*pow(ANS_UP[x],mod-2,mod)*pow(Combi(Children[P[x]]-1,Children[x]),mod-2,mod)%mod

for i in range(1,N+1):
    if i==1:
        print(ANS_UP[1])
    else:
        ANS=ANS_DOWN[i]%mod

        sumchild=0
        for to in E[i]:
            if to==P[i]:
                sumchild+=N-Children[i]
                ANS=ANS*Combi(sumchild,N-Children[i])%mod
            else:                  
                sumchild+=Children[to]
                ANS=ANS*ANS_UP[to]*Combi(sumchild,Children[to])%mod

        print(ANS)