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 java.math.BigInteger;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    private static final int p = 1_000_000_007;
    private static final BigInteger bigP = BigInteger.valueOf(p);
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        LinkedList<Integer>[] neighbours = new LinkedList[n];
        for (int i = 0; i < n; i++) {
            neighbours[i] = new LinkedList<>();
        }
        boolean[] visited = new boolean[n];

        long[] factors = new long[n];
        long[] revFactors = new long[n];
        factors[0]=1;
        factors[1]=1;
        revFactors[0]=1;
        revFactors[1]=1;
        long tmp=1;
        for (int i = 2; i < n; i++) {
            tmp = tmp*i%p;
            factors[i] = tmp;
            revFactors[i] = BigInteger.valueOf(tmp).modInverse(bigP).intValue();
        }



        for (int i = 0; i < n - 1; i++) {
            int a = scanner.nextInt()-1;
            int b = scanner.nextInt()-1;
            neighbours[a].add(b);
            neighbours[b].add(a);
        }

        int[] nodesInSubtree = new int[n];
        long[] numberWays = new long[n];



        Stack<Integer> stack = new Stack<>();
        stack.add(0);
        while (!stack.isEmpty()){
            Integer pop = stack.peek();
            if(!visited[pop]){
                visited[pop] = true;
                for (Integer neighbour : neighbours[pop]) {
                    if(!visited[neighbour]) stack.push(neighbour);
                }
            }else{
                nodesInSubtree[pop]=0;
                numberWays[pop]=1;
                for (Integer neighbour : neighbours[pop]) {
                    if(!visited[neighbour]){
                        numberWays[pop] =
                                numberWays[pop]
                                    *factors[nodesInSubtree[pop]+nodesInSubtree[neighbour]] %p
                                    *revFactors[nodesInSubtree[pop]] %p
                                    *revFactors[nodesInSubtree[neighbour]] %p
                                    *numberWays[neighbour] %p;
                        nodesInSubtree[pop]+=nodesInSubtree[neighbour];
                    }
                }
                visited[pop] = false;
                nodesInSubtree[pop]++;
                stack.pop();
            }
        }

//        System.out.println(Arrays.toString(nodesInSubtree));
//        System.out.println(Arrays.toString(numberWays));

        stack.add(0);
        while (!stack.isEmpty()){
            Integer pop = stack.pop();
            visited[pop] = true;
            for (Integer neighbour : neighbours[pop]) {
                if(visited[neighbour]){
                    numberWays[pop] = numberWays[neighbour]
                            * factors[n-nodesInSubtree[pop]-1] % p
                            * factors[nodesInSubtree[pop]] % p
                            * revFactors[nodesInSubtree[pop]-1] % p
                            * revFactors[n-nodesInSubtree[pop]] % p;
                }else{
                    stack.push(neighbour);
                }
            }
        }

        for (long numberWay : numberWays) {
            System.out.println(numberWay);
        }
    }
}
