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
from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n = int(input())
G = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)

mod = 10**9 + 7
queue = deque()
queue.append(0)
parent = [-1]*n
parent[0] = 0
while queue:
    now = queue.popleft()
    for to in G[now]:
        if parent[to] == -1:
            parent[to] = now
            queue.append(to)

data1 = [[0,0] for i in range(n)]
def factorial(N,MOD,r=True):
    fact = [1]*(N+1)
    rfact = [1]*(N+1)
    r = 1
    for i in range(1,N+1):
        fact[i] = r = r * i % MOD
    rfact[N] = r = pow(fact[N],MOD-2,MOD)
    for i in range(N, 0, -1):
        rfact[i-1] = r = r * i % MOD
    if r:
        return fact,rfact
    else:
        return fact

fact,rfact = factorial(2*10**5,mod)
def com(l):
    res = 1
    s = 0
    for x in l:
        res *= rfact[x]
        res %= mod
        s += x
    res *= fact[s]
    res %= mod
    return res
def dfs(now,pre):
    if data1[now] != [0,0]:
        return
    if len(G[now]) == 1 and G[now][0] == pre:
        data1[now] = [1,1]
        return
    x,y = 0,1
    child = []
    for to in G[now]:
        if pre == to:
            continue
        dfs(to,now)
        child.append(data1[to][1])
        y *= data1[to][0]
        y %= mod
    res = y * com(child)
    res %= mod
    data1[now] = [res,sum(child)+1]
    return

dfs(0,-1)

ans = [data1[i][0] for i in range(n)]

que = deque()
que.append([0,0])
while que:
    now,pre = que.popleft()
    for to in G[now]:
        if to == pre:continue
        ans[to] = ans[now]*data1[to][1]*pow(n-data1[to][1],mod-2,mod)
        ans[to] %= mod
        que.append([to,now])

for x in ans:
    print(x)