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 rerooting(n, edges, identity, merge, add_node):
    # 全方位木 dp
    # 参考: https://qiita.com/keymoon/items/2a52f1b0fb7ef67fb89e
    G = [[] for _ in range(n)]
    G_idxs = [[] for _ in range(n)]  # 自分を指すノードのインデックス
    for a, b in edges:
        G_idxs[a].append(len(G[b]))
        G_idxs[b].append(len(G[a]))
        G[a].append(b)
        G[b].append(a)
    # step 1
    parents = [0] * n
    order = []  # 行きがけ順
    stack = [0]
    parents[0] = -1
    while stack:
        v = stack.pop()
        p = parents[v]
        order.append(v)
        for u in G[v]:
            if p != u:
                stack.append(u)
                parents[u] = v
    subtree_res = [[0]*len(Gv) for Gv in G]
    # 下から登る
    for v in order[:0:-1]:
        p = parents[v]
        result = identity
        for idx_Gv, (u, subtree_res_v_i) in enumerate(zip(G[v], subtree_res[v])):
            if p == u:
                parent_idx = idx_Gv
            else:
                result = merge(result, subtree_res_v_i)
        idx_p2v = G_idxs[v][parent_idx]
        subtree_res[p][idx_p2v] = add_node(result, v)
    # step 2
    # 上から降りる
    results = [0] * n
    for v in order:
        subtree_res_v = subtree_res[v]
        cum = identity
        cum_from_tail = [identity]
        for r in subtree_res_v[:0:-1]:
            cum = merge(r, cum)
            cum_from_tail.append(cum)
        cum_from_tail.reverse()
        cum = identity
        for r, cum_t, u, idx_u2v in zip(subtree_res_v, cum_from_tail, G[v], G_idxs[v]):
            result = add_node(merge(cum, cum_t), v)
            subtree_res[u][idx_u2v] = result
            cum = merge(cum, r)
        results[v] = add_node(cum, v)
    return results


class Combination:
    def __init__(self, n_max, mod=10**9+7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    def __call__(self, n, r):  # self.C と同じ
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

def main():
    N = int(input())
    AB = [list(map(lambda x: int(x)-1, input().split())) for _ in range(N-1)]
    mod = 10**9 + 7
    comb = Combination(202020)
    identity = (1, 0)
    merge = lambda a, b: (a[0] * b[0] % mod * comb(a[1]+b[1], a[1]) % mod, a[1] + b[1])
    add_node = lambda value, idx: (value[0], value[1]+1)
    Ans = rerooting(N, AB, identity, merge, add_node)
    print("\n".join(str(ans) for ans, _ in Ans))

main()
