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(1000000)
mod = 7 + 10 ** 9
from collections import deque

def comb(n, r, fact, revfact, mod):
    return (fact[n] * revfact[n-r] * revfact[r]) % mod

def dfs1(i, pre, Edge, Dist, Son, fact, revfact):
    under = 0
    for ne in Edge[i]:
        if ne != pre:
            sonNum = dfs1(ne, i, Edge, Dist, Son, fact, revfact)
            under += sonNum
            Dist[i] *= (comb(under, sonNum, fact, revfact, mod) * Dist[ne]) % mod
            Dist[i] %= mod
    Son[i] = under
    return under + 1 

def solve():
    input = sys.stdin.readline
    N = int(input())
    Edge = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        Edge[a-1].append(b-1)
        Edge[b-1].append(a-1)
    fact = [1] * (N + 1)
    for i in range(1, N + 1): fact[i] = (fact[i-1] * i) % mod
    revfact = [1] * (N + 1)
    revfact[N] = pow(fact[N], mod - 2, mod)
    for i in reversed(range(1, N)): revfact[i] = ((i + 1) * revfact[i+1]) % mod

    Dist = [1] * N
    Son = [0] * N
    dfs1(0, 0, Edge, Dist, Son, fact, revfact)
    q = deque()
    for ne in Edge[0]:
        q.append((ne, 0))
    while q:
        ne, pre = q.pop()
        upper = (Dist[pre] * pow(comb(N - 1, Son[ne] + 1 , fact, revfact, mod), mod - 2, mod)) % mod
        Dist[ne] = (upper * comb(N - 1, N - 1- Son[ne], fact, revfact, mod)) % mod
        for nextEdge in Edge[ne]:
            if nextEdge != pre: q.append((nextEdge, ne))
    print("\n".join(map(str, Dist)))

    return 0

if __name__ == "__main__":
    solve()