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

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
g = []
for i in range(n): g.append([])
for i in range(n-1):
    x, y = na()
    x -= 1
    y -= 1
    g[x].append(y)
    g[y].append(x)

dp = [0] * n
ep = [0] * n
des = [0] * n

def enumfif(n, mod):
    f = [0] * (n+1)
    invf = [0] * (n+1)
    f[0] = 1
    for i in range(1, n+1):
        f[i] = f[i-1] * i % mod

    a = f[n]
    b = mod
    p, q = 1, 0
    while b > 0:
        c = a//b
        d = a; a = b; b = d % b
        d = p; p = q; q = d-c*q
    invf[n] = p + mod if p < 0 else p
    for i in range(n-1,-1,-1):
        invf[i] = invf[i+1] * (i+1) % mod
    return f, invf

def C(n, r, mod, fif):
    if n < 0 or r < 0 or r > n:
        return 0
    return fif[0][n] * fif[1][r] * fif[1][n-r] % mod

mod = 1000000007
fif = enumfif(200005, mod)

sys.setrecursionlimit(200005)

def dfs(cur, pre, g):
    val = 1
    de = 0
    for e in g[cur]:
        if e == pre: continue
        dfs(e, cur, g)
        de += des[e]
        val = val * dp[e] * C(de, des[e], mod, fif) % mod
    dp[cur] = val
    des[cur] = de + 1

def dfs2(cur, pre, g):
    # print(cur, pre)
    for e in g[cur]:
        if e == pre: continue
        val = dp[cur] * fif[1][n-1] * fif[0][n-des[e]-1] * fif[0][des[e]] % mod
        dp[e] = val * C(n-1, n-des[e], mod, fif) % mod
        # val = dp[cur] * fif[1][n-1] * fif[0][n-des[e]-1] * fif[0][des[e]] * invl(dp[e], mod) % mod
        # dp[e] = dp[e] * val * C(n-1, n-des[e], mod, fif) % mod
        dfs2(e, cur, g)

def invl(a, mod):
    b = mod
    p = 1; q = 0
    while b > 0:
        c = a // b
        a, b = b, a%b
        p, q = q, p-c*q
    return p + mod if p < 0 else p


dfs(0, -1, g)
dfs2(0, -1, g)
for val in dp:
    print(val)
