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>
using namespace std;
typedef long long ll;
#define endl '\n'
const int INF=1e9+5;
const int N=2e5+5;
const int mod=1e9+7;

ll n;
vector<ll> v[N];
ll fac[N],finv[N],inv[N];
vector<ll> dp(N,-1);
ll sizee[N];
vector<ll> ans(N,-1);

void init(){
	fac[0]=fac[1]=1;
	finv[0]=finv[1]=1;
	inv[1]=1;
	for(ll i=2;i<N;++i){
		fac[i]=fac[i-1]*i%mod;
		inv[i]=mod-inv[mod%i]*(mod/i)%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
	}
}

pair<ll,ll> solve(ll u,ll par){
	if(dp[u]!=-1) return pair<ll,ll>(dp[u],sizee[u]);
	ll res=1;
	vector<ll> sz;
	for(ll x:v[u]){
		if(x==par) continue;
		if(res==0) res=1;
		pair<ll,ll> p=solve(x,u);
		res=(res*p.first)%mod;
		sizee[u]+=p.second+1;
		sz.push_back(p.second+1);
	}
	res=(res*fac[sizee[u]])%mod;
	for(ll x:sz){
		// res/=fac[x]
		res=(res*finv[x])%mod;
	}
	dp[u]=res;
	return pair<ll,ll> (dp[u],sizee[u]);
}

ll poww(ll a,ll b){
	ll r=1;
	while(b){
		if(b&1) r=(r*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return r;
}

void dfs(ll u,ll par){
	ans[u]=dp[u];
	if(par!=-1){
		ans[u]=(ans[u]*(sizee[u]+1))%mod;
		ans[u]*=ans[par]*poww(dp[u],mod-2)%mod;
		ans[u]%=mod;
		ans[u]*=inv[n-1-sizee[u]];
		ans[u]%=mod;
	}
	for(ll x:v[u]){
		if(x!=par) dfs(x,u);
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	init();
	cin>>n;
	for(ll i=0;i<n-1;++i){
		int x,y;
		cin>>x>>y;
		--x;
		--y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	solve(0,-1);
	dfs(0,-1);
	for(int i=0;i<n;++i) cout<<ans[i]<<" ";
	return 0;
}
