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
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

def solve():
    N = int(input())
    AB = [tuple(map(int,input().split())) for i in range(N-1)]
    es = [[] for i in range(N)]
    for i,(a,b) in enumerate(AB):
        a,b = a-1,b-1
        es[a].append((b,i))
        es[b].append((a,i))
    MOD = 10**9+7

    size = [-1] * N
    def calc_size(v,p=-1):
        ret = 1
        for to,_ in es[v]:
            if to==p: continue
            ret += calc_size(to,v)
        size[v] = ret
        return ret
    calc_size(0)

    MAXN = N+5
    fac = [1,1] + [0]*MAXN
    finv = [1,1] + [0]*MAXN
    inv = [0,1] + [0]*MAXN
    for i in range(2,MAXN+2):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = -inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i-1] * inv[i] % MOD

    dpdn = [0] * (N-1)
    dn = set()
    def dfs(v,p=-1):
        ret = fac[size[v]-1]
        for to,i in es[v]:
            if to==p: continue
            dn.add((v,to))
            dpdn[i] = dfs(to,v)
            ret *= finv[size[to]] * dpdn[i]
        ret %= MOD
        return ret
    dfs(0)

    dpup = [0] * (N-1)
    from collections import deque
    q = deque([(0,-1)])
    while q:
        v,p = q.popleft()
        whole = 1
        for to,i in es[v]:
            if to != p:
                whole *= finv[size[to]] * dpdn[i]
            else:
                whole *= finv[N-size[v]] * dpup[i]
        whole %= MOD
        for to,i in es[v]:
            if to==p: continue
            dpup[i] = (whole * fac[N-size[to]-1] * fac[size[to]] * pow(dpdn[i], MOD-2, MOD)) % MOD
            q.append((to,v))

    ans = []
    for v in range(N):
        a = 1
        s = 0
        for to,i in es[v]:
            if (v,to) in dn:
                s += size[to]
                a *= finv[size[to]] * dpdn[i]
            else:
                s += N-size[v]
                a *= finv[N-size[v]] * dpup[i]
            a %= MOD
        a *= fac[s]
        ans.append(a%MOD)
    print(*ans, sep='\n')

solve()