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
n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
mod = 10**9 + 7
factorial = [1]*(n+1)
factorial_inv = [1]*(n+1)
for i in range(1,n+1):
    factorial[i] = factorial[i-1]*i%mod
factorial_inv[n] = pow(factorial[n],mod-2,mod)
for i in range(n,0,-1):
    factorial_inv[i-1] = factorial_inv[i]*i%mod

pa = [0]*(n+1)
dp = [1]*(n+1)
size = [1]*(n+1)
checked = []
stack = [i]
while stack:
    a = stack.pop()
    checked.append(a)
    for j in graph[a]:
        if pa[a] == j:   
            continue
        else:
            stack.append(j)
            pa[j] = a

for i in checked[::-1]:
    p = pa[i]
    s = size[i]
    dp[i] *= factorial[s-1]
    dp[i] %= mod
    dp[p] *= dp[i]*factorial_inv[s]
    dp[p] %= mod
    size[p] += s

size_ = [n-i+1 for i in size]
dp_ = [1]*(n+1)
for i in checked[1:]:
    p = pa[i]
    dp_[i] *= dp[p]
    dp_[i] *= factorial_inv[size[p]-1]
    dp_[i] *= pow(dp[i],mod-2,mod)
    dp_[i] *= factorial[size[i]]
    dp_[i] *= dp_[p]
    dp_[i] *= factorial_inv[size_[p]-1]
    dp_[i] *= factorial[size_[i]-2]
    dp_[i] %= mod
    
for i in range(1,n+1):
    ans = factorial[n-1]*dp[i]*dp_[i]*factorial_inv[size[i]-1]*factorial_inv[size_[i]-1]
    ans %= mod
    print(ans)