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)
from collections import deque
MOD = 1000000007

N =  int(input())
childs = [[] for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    childs[a].append(b)
    childs[b].append(a)

dp = [0] * (N + 1) # represent the # if i is the root (1)
tree_size = [0]*(N + 1)
ans = [0] * (N + 1)

n_inv = [1, 1]
n_j_mod = [1, 1]

for i in range(2, N+1):
    n_inv.append((pow(i, MOD-2, MOD) * n_inv[-1]) % MOD)
    n_j_mod.append((n_j_mod[-1] * i) % MOD)


def dfs(i, father=-1):
    method_num = 1
    t_size = 1
    for child in childs[i]:
        if child != father:
            num, size = dfs(child, i)
            method_num = (method_num * num * n_inv[size]) % MOD
            t_size += size
    method_num = (method_num * n_j_mod[t_size - 1]) % MOD
    dp[i] = method_num
    tree_size[i] = t_size
    return method_num, t_size

def rdfs(i, f_num, father=-1):
    ans[i] = (dp[i] * f_num * n_j_mod[N-1] * n_inv[N - tree_size[i]] * n_inv[tree_size[i] - 1]) % MOD

    for child in childs[i]:
        if child != father:
            cf_num = (ans[i] * n_j_mod[tree_size[child]] * n_j_mod[N - tree_size[child] - 1] * n_inv[N - 1] * pow(dp[child], MOD-2, MOD)) % MOD
            rdfs(child, cf_num, i)
dfs(1)

rdfs(1, 1)
print('\n'.join(list(map(str, ans[1:]))))
