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
# -*- coding: utf-8 -*-
import sys
from functools import reduce

MAX_INT = 2**62-1
sys.setrecursionlimit(10**7)

input = sys.stdin.readline

# @profile
MOD = 10**9 + 7


def mul_mod(*args, mod=MOD):
    return reduce(lambda a, b: a * b % mod, args)


def solve(g, f, fi, m):
    mul = mul_mod

    stack = [(0, 1)]
    pre_order = []
    n = len(g) - 1

    while stack:
        pre, cur = stack.pop()
        pre_order.append((pre, cur))

        for nxt in g[cur]:
            if nxt == pre:
                continue
            stack.append((cur, nxt))

    size = [1] * (n+1)
    dp = [1] * (n+1)

    for pre, cur in reversed(pre_order):
        dp[cur] = mul(dp[cur], f[size[cur]-1])
        dp[pre] = mul(dp[pre], dp[cur], fi[size[cur]])
        size[pre] += size[cur]

    ans = [1] * (n+1)
    ans[1] = dp[1]

    for pre, cur in pre_order[1:]:
        i = size[cur]
        temp = mul(ans[pre], f[n-i-1], fi[n-1], f[i], pow(dp[cur], m-2, m))
        ans[cur] = mul(f[n-1], temp, fi[n-i], dp[cur], fi[i-1])
    print(*ans[1:], sep='\n')


# @profile
def main():
    mul = mul_mod
    mod = MOD
    n = int(input())
    g = [[] for _ in range(n+1)]

    fact = [1] * (n+1)
    fact_inv = [0] * (n+1)

    for i in range(1, n+1):
        fact[i] = mul(fact[i-1], i)

    fact_inv[-1] = pow(fact[-1], mod-2, mod)

    for i in range(n)[::-1]:
        fact_inv[i] = mul(fact_inv[i+1], (i+1))

    for _ in range(n-1):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)

    solve(g, fact, fact_inv, mod)


if __name__ == "__main__":

    main()
