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>
#define rep(i,n) for(int i=0; i<(int)(n); i++)

using namespace std;
typedef long long LL;
const int Max_Num=2e5+10;
const LL mod=1e9+7;
int N;
LL F[Max_Num], Finv[Max_Num];
LL C[Max_Num], dp[Max_Num];
vector<int> G[Max_Num];

LL modinv(LL x){
	LL m=mod, u=1, v=0;
	while(m){
		LL t=x/m;
		x-=t*m; swap(x,m);
		u-=t*v; swap(u,v);
	}
	u%=mod;
	if(u<0) u+=mod;
	return u;
}

void fact(){
	F[0]=1;
	rep(i,Max_Num-1){
		F[i+1]=F[i]*(i+1);
		F[i+1]%=mod;
	}
	rep(i,Max_Num) Finv[i]=modinv(F[i]);
}

LL comb(LL n, LL k){
	LL res=F[n];
	res*=Finv[k]*Finv[n-k]%mod;
	return res%mod;
}

void child(int v, int par=-1){
	int n=G[v].size();
	if(v!=0 && n==1) return;
	LL res=0;
	rep(i,n){
		int next=G[v][i];
		if(next==par) continue;
		child(next, v);
		res+=C[next]+1;
	}
	C[v]=res;
}

void dfs(int v, int par=-1){
	int n=G[v].size();
	if(v!=0 && n==1){
		dp[v]=1;
		return;
	}
	LL res=F[C[v]];
	rep(i,n){
		int next=G[v][i];
		if(next==par) continue;
		dfs(next, v);
		res*=dp[next]*Finv[C[next]+1]%mod;
		res%=mod;
	}
	dp[v]=res%mod;
}

void bfs(int v, int par=-1){
	int n=G[v].size();
	if(par!=-1){
		LL res=dp[par]*modinv(dp[v])%mod;
		res*=modinv(comb(N-1,C[v]+1));
		dp[v]*=res%mod;
		dp[v]%=mod;
	}
	dp[v]*=comb(N-1,N-1-C[v]);
	dp[v]%=mod;
	rep(i,n){
		int next=G[v][i];
		if(next==par) continue;
		bfs(next, v);
	}
}

int main(){
	fact();
	cin >> N;
	rep(i,N-1){
		int a, b;
		cin >> a >> b;
		a--; b--;
		G[a].emplace_back(b);
		G[b].emplace_back(a);
	}
	rep(i,N) dp[i]=0, C[i]=0;
	child(0);
	dfs(0);
	bfs(0);
	rep(i,N) cout << dp[i] << endl;

	return 0;
}