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)
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n_ = 2 * 10**5 + 20
mod = 10**9 + 7
fun = [1] * (n_ + 1)
for i in range(1, n_ + 1):
    fun[i] = fun[i - 1] * i % mod
rev = [1] * (n_ + 1)
rev[n_] = pow(fun[n_], mod - 2, mod)
for i in range(n_ - 1, 0, -1):
    rev[i] = rev[i + 1] * (i + 1) % mod

def modinv(x, mod):
    x %= mod
    a, b = x, mod
    u, v = 1, 0
    while b:
        t = a // b
        a -= t * b; a, b = b, a
        u -= t * v; u, v = v, u
    return u % mod

def nCr(n, r):
    if r > n:
        return 0
    return fun[n] * rev[r] % mod * rev[n - r] % mod

n = ni()
g = [list() for _ in range(n)]
for _ in range(n-1):
    a,b = nm()
    a -= 1; b -= 1
    g[a].append(b)
    g[b].append(a)

sl = [1]*n
pm = [1]*n
def dfs(v, p):
    for x in g[v]:
        if x == p:
            continue
        dfs(x, v)
        sl[v] += sl[x]
        pm[v] = pm[v] * pm[x] % mod
    sv = sl[v] - 1
    for x in g[v]:
        if x == p:
            continue
        pm[v] = pm[v] * nCr(sv, sl[x]) % mod
        sv -= sl[x]
    return

def dfs2(v, p):
    pp = pm[p] *  modinv(nCr(n-1, sl[v]) * pm[v], mod) % mod
    sp = n - sl[v]
    pm[v] = pm[v] * pp % mod * nCr(n-1, sp) % mod
    for x in g[v]:
        if x == p:
            continue
        dfs2(x, v)

dfs(0, -1)
for x in g[0]:
    dfs2(x, 0)

print(*pm, sep = '\n')
