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 ** 6)


MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


def dfs(v):
    global MOD
    childs = 0
    var = 1
    for e in edge[v]:
        if path[e] == 0:
            path[e] = 1
            nc, nvar = dfs(e)
            childs += nc
            V[v][e] = (nc, nvar)
            var *= nvar
            var %= MOD
            var *= invs[nc]
            var %= MOD
    var *= modFacts[childs]
    var %= MOD
    dp[v] = (childs, var)
    return childs + 1, var


def dfs2(v, pn, pVar):
    global MOD
    oNodes, oVar = dp[v]
    tNodes = pn + oNodes
    tVar = (oVar * pVar) % MOD
    tVar *= invs[oNodes]
    tVar %= MOD
    tVar *= modFacts[tNodes]
    tVar %= MOD
    tVar *= invs[pn]
    tVar %= MOD

    dp[v] = (tNodes, tVar)

    for e in V[v].keys():
        eNodes, eVar = V[v][e]
        nVar = (tVar * invs[tNodes]) % MOD
        nVar *= modFacts[eNodes]
        nVar %= MOD
        nVar *= modFacts[tNodes - eNodes]
        nVar %= MOD
        nVar *= pow(eVar, MOD - 2, MOD)
        nVar %= MOD
        dfs2(e, tNodes - eNodes + 1, nVar)


N = int(input())
edge = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = map(int, s.split())
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

modFacts, invs = prepare(N)

V = [{} for _ in range(N)]
path = [0] * N
dp = [None] * N
path[0] = 1
dfs(0)
dfs2(0, 0, 1)


for i in range(N):
    print(dp[i][1])
