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
def main():
    from sys import stdin
    input = stdin.readline
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]

    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]

    mod = 10**9+7
    fact = [1, 1]
    inv = [pow(i, mod-2, mod) for i in range(n+1)]
    for i in range(2, n+1):
        fact.append(fact[-1]*i % mod)

    def Reroot():
        # merge:頂点aにbをマージするときのモノイド
        # adj_bu:ボトムアップ時の調整（a:値,i:頂点）
        # adj_td:トップダウン時の調整（a:値,i:頂点,p:親）
        # （根方向への調整と考えるとわかりやすい）
        # adj_fin:最終調整（a:値,i:頂点）
        def merge(a, b): return a * b % mod
        def adj_bu(a, i): return a * inv[size[i]] % mod
        def adj_td(a, i, p): return a * inv[n-size[i]] % mod
        def adj_fin(a, i): return a * fact[n-1] % mod

        # トポロジカルソートをする
        # T:木の隣接グラフ表現をset化
        # P:親
        # q:キュー
        # order:トポソしたもの
        T = g
        P = [-1]*n
        q = [0]
        ini = 1
        order = []
        while q:
            i = q.pop()
            order.append(i)
            for a in T[i]:
                if a != P[i]:
                    P[a] = i
                    T[a].remove(i)
                    q.append(a)

        T = [list(i) for i in T]

        # サイズの処理を先に行う
        # size[i]:0を根とする根付き木における、iを根とする部分木の大きさ
        size = [1]*n
        for i in order[1:][::-1]:
            size[P[i]] += size[i]

        # ボトムアップ処理をする
        # ME:マージした値を一時保存
        # DP:DP値、MEを調整したもの
        ME = [ini]*n
        DP = [0]*n
        for i in order[1:][::-1]:
            DP[i] = adj_bu(ME[i], i)
            p = P[i]
            ME[p] = merge(ME[p], DP[i])
        DP[order[0]] = adj_fin(ME[order[0]], order[0])
        TD = [ini]*n

        # トップダウン処理をする
        for i in order:
            # 左からDP（結果はTDに入れている）
            ac = TD[i]
            for j in T[i]:
                TD[j] = ac
                ac = merge(ac, DP[j])
            # 右からDP（結果はacに入れている、一度しか使わないのでacで問題ない）
            # 例えばjが1から4だったとすると、TD[j]にはそれぞれ
            # TD[1] = 無、TD[2] = DP[1]、TD[3] = DP[1]*DP[2]、TD[4] = DP[1]*DP[2]*DP[3]
            # が入っている。
            # ここでacにそれぞれ無、DP[4]、DP[3]*DP[4]、DP[2]*DP[3]*DP[4]を
            # 順に入れていくといい感じになることがわかる。
            # 最後にTDに欠けているのは本来の根方向への補正なので、
            # jの部分木以外のサイズの逆数を掛けてやる必要がある。
            # これで、TDには根方向、MEにはそれ以外の方向のDP値が入っている状態になっているので
            # あとは掛けてやるだけでよい。
            ac = ini
            for j in T[i][::-1]:
                TD[j] = adj_td(merge(TD[j], ac), j, i)
                ac = merge(ac, DP[j])
                DP[j] = adj_fin(merge(ME[j], TD[j]), j)
        for i in DP:
            print(i)
    Reroot()


main()
