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 os, sys, bisect, copy
from collections import defaultdict, Counter, deque
from functools import lru_cache   #use @lru_cache(None)
if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')
#
def input(): return sys.stdin.readline()
def mapi(arg=0): return map(int if arg==0 else str,input().split())
#------------------------------------------------------------------
sys.setrecursionlimit(100005)
mod = 1000000007
N=int(2*1e5+100)
sz = [0]*N
dp = [0]*N
gr = defaultdict(list)
def modPow(a,b):
    ans=1
    while (b):
        if (b&1): ans=(ans*a)%mod
        b>>=1
        a=(a*a)%mod
    return ans

def modInv(x):
    return modPow(x,mod-2)

def dfs(x, par):
    sz[x]=1
    for item in gr[x]:
        if item==par: continue
        dfs(item,x)
        sz[x]+=sz[item]

def dfs1(x, par):
    for item in gr[x]:
        if item==par: continue
        dp[item]=(dp[x]*(n-sz[item]))%mod
        dp[item]=(dp[item]*modInv(sz[item]))%mod
        dfs1(item,x)

n = int(input())
for i in range(n-1):
    x,y = mapi()
    gr[x].append(y)
    gr[y].append(x)
dfs(1,0)
dp[1]=1
for i in range(1,n+1):
    dp[1]=(dp[1]*sz[i])%mod
dfs1(1,0)
res = 1
for i in range(1,n+1):
    res = (res*i)%mod
for i in range(1,n+1):
    dp[i]=(res*modInv(dp[i]))%mod
for i in range(1,n+1):
    print(dp[i])
