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
#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

const int MOD=1e9+7;
vector<int> adj[200000];
int F[200001], Finv[200001], D[200000], W[200000];

int mul(int a, int b)
{
	return 1LL*a*b%MOD;
}

int nCr(int n, int r)
{
	return mul(F[n],mul(Finv[r],Finv[n-r]));
}

int nCrinv(int n, int r)
{
	return mul(Finv[n],mul(F[r],F[n-r]));
}

void dfs(int c)
{
	W[c]=D[c]=1;
	for(auto n: adj[c]) if(W[n]==0) {
		dfs(n);
		D[c]=mul(nCr((W[c]+=W[n])-1,W[n]),mul(D[c],D[n]));
	}
}

void dfs2(int c)
{
	for(auto n: adj[c]) if(W[n]<W[c]) {
		D[n]=mul(mul(D[c],nCrinv(W[0]-1,W[n])),nCr(W[0]-1,W[0]-W[n]));
		dfs2(n);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N;
	cin>>N;
	F[0]=Finv[0]=1;
	for(int i=1;i<=200000;i++) F[i]=mul(F[i-1],i);
	Finv[200000]=750007460;
	for(int i=200000;--i;) Finv[i]=mul(Finv[i+1],i+1);
	for(int i=1;i<N;i++) {
		int a, b;
		cin>>a>>b;
		adj[--a].push_back(--b);
		adj[b].push_back(a);
	}
	dfs(0); dfs2(0);
	for(int i=0;i<N;i++) cout<<D[i]<<'\n';
	return 0;
}