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
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x : int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)

mod = 10**9+7
fact = [1] * N
fact_inv = [1] * N
inv = lambda x : pow(x, mod-2, mod)
for i in range(1, N):
    fact[i] = i * fact[i-1] % mod
    fact_inv[i] = inv(fact[i])
comb = lambda n, k : fact[n] * fact_inv[k] * fact_inv[n-k] % mod

value = [1] * N
count = [0] * N
def dfs(par, v):
    for u in G[v]:
        if par == u:
            continue
        dfs(v, u)
        count[v] += count[u]
        value[v] = value[v] * value[u] * comb(count[v], count[u]) % mod
    count[v] += 1

ans = [0] * N
def reroot(par, val_par, cnt_par, v):
    ans[v] = val_par * value[v] * comb(N-1, cnt_par) % mod
    for u in G[v]:
        if par == u:
            continue
        val = ans[v] * inv(value[u] * comb(N-1, count[u])) % mod
        reroot(v, val, N-count[u],  u)

dfs(-1, 0)
reroot(-1, 1, 0, 0)
print(*ans, sep='\n')