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 ** 7)
class Tree:
  C, RL = {}, {}
  R, N, D, S, P, T = None, None, None, None, None, None
  TL = None
  def __init__(s, num):
    s.N = num
  def set(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def makeRank(s, root):
    s.R = [0] * s.N #各ノードのランク
    s.R[root] = 1
    s.RL[1] = [root] #各ランクのノード
    s.S = {} #各ノードの子ノード
    s.P = [-1] * s.N #各ノードの親ノード
    s.D = 1
    while s.RL[s.D] != []:
      s.D += 1
      s.RL[s.D] = []
      for i in s.RL[s.D - 1]:
        for j in s.C[i]:
          if s.R[j] == 0:
            s.R[j] = s.D
            s.RL[s.D].append(j)
            if i not in s.S: s.S[i] = [j]
            else: s.S[i].append(j)
            s.P[j] = i      
  def bottomUpDP(s):
    for i in range(s.D - 2, 0, -1):
      T = s.RL[i]
      for j in T:
        if j not in s.S: continue
        for k in s.S[j]:
          s.dp_sub_exe(j, k)
  def topDownDP(s):
    for i in range(2, s.D):
      T = s.RL[i]
      for j in T:
        s.dp_sub_exe_inv(j, s.P[j])
  def allDP(s):
    s.dp_init()
    s.bottomUpDP()
    s.topDownDP()
    return s.DP
  def dp_init(s): #単位元で初期化
    s.DP = [1] * N
    s.sDP = [1] * N
  def dp_sub_exe(s, x, y): #ボトムアップの処理
    s.sDP[x] += s.sDP[y]
    s.DP[x] = s.DP[x] * s.DP[y] * com.com(s.sDP[x] - 1, s.sDP[y]) % MOD
  def dp_sub_exe_inv(s, x, y): #トップダウンの処理
    t = com.com(s.sDP[y] - 1, s.sDP[x]) * s.DP[x] % MOD
    t = s.DP[y] * s.inv(t, MOD)
    k = s.sDP[y] - s.sDP[x]
    k = com.com(s.sDP[y] - 1, k) % MOD
    s.sDP[x] = s.sDP[y]
    s.DP[x] = s.DP[x] * t * k % MOD
  def inv(s, a, mod): #逆元
    return pow(a, mod - 2, mod)
  
class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD

N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]

MOD = 10 ** 9 + 7
com = comb(N, MOD)

T = Tree(N)
for a, b in ab:
  a -= 1
  b -= 1
  T.set(a, b)

T.makeRank(0)
DP = T.allDP()

for i in DP:
  print(i)