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
from collections import deque
sys.setrecursionlimit(1000000)

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

def dfs(i, parent, DP, sNum, E, fact, revfact, mod):
    Ans = 1
    sonNode = 1
    S = []
    for e in E[i]:
        if e != parent:
            mult, sn = dfs(e, i, DP, sNum, E, fact, revfact, mod)
            S.append(sn)
            Ans *= mult
            Ans %= mod
            sonNode += sn
    stotal = sonNode - 1
    for s in S:
        Ans *= comb(stotal, s, fact, revfact, mod)
        Ans %= mod
        stotal -= s
    DP[i] = Ans
    sNum[i] = sonNode - 1
    return Ans, sonNode

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

    DP = [1] * N
    sNum = [0] * N
    usNum = [0] * N
    dfs(0, 0, DP, sNum, E, fact, revfact, mod)
    q = deque()
    for e in E[0]: q.append((e, 0))
    while q:
        nn, parn = q.popleft()
        upperMult = DP[parn] * pow(comb(N-1, sNum[nn] + 1, fact, revfact, mod), mod - 2, mod)
        usNum[nn] = upperNum = sNum[parn] - sNum[nn] + usNum[parn]
        DP[nn] = (upperMult * comb(N-1, upperNum, fact, revfact, mod)) % mod
        for e in E[nn]:
            if e != parn: q.append((e, nn))
        
    print("\n".join(map(str, DP)))
      
    return 0

if __name__ == "__main__":
    solve()
