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;
typedef pair<ll,int>pii;
typedef vector<int>vi;

#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define fi first
#define se second
#define de(x) cout<<#x<<"="<<x<<"\n"
#define dd(x) cout<<#x<<"="<<x<<" "
#define pb(x) push_back(x)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define lowbit(a) ((a)&-(a))
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
const int N=2e6+5;
const int mod = 1e9 + 7;
int f[N],invf[N];
int qpow(int x,int n){
	int res = 1;
	while(n){
		if(n&1)res = (ll)res*x%mod;
		x = (ll)x*x%mod;
		n >>= 1;
	}
	return res;
}
void init(){
	f[0] = invf[0] = 1;
	rep(i , 1 ,N)
		f[i] = (ll)f[i-1]*i%mod,invf[i] = qpow(f[i],mod - 2);
}
vi g[N];
int n,big[N],dp[N];
void dfs(int u,int p){
	big[u] = dp[u] = 1;
	for(auto v:g[u]){
		if(v == p)continue;
		dfs(v,u);
		big[u] += big[v];
		dp[u] = (ll)dp[u]*dp[v]%mod;
		dp[u] = (ll)dp[u]*invf[big[v]]%mod;
	}
	dp[u] = (ll)dp[u]*(f[big[u] - 1])%mod;
}
int ans[N];
void dfs1(int u,int p){
	if(u!= 1){
		ans[u] = (ll)ans[p]*invf[n - big[u]]%mod;
		ans[u] = (ll)ans[u]*f[n - big[u] - 1]%mod;
		ans[u] = (ll)ans[u]*f[big[u]]%mod;
		ans[u] = (ll)ans[u]*qpow(dp[u],mod - 2)%mod;
		dp[u] = (ll)dp[u]*(invf[big[u] - 1])%mod;
		ans[u] = (ll)ans[u]*dp[u]%mod;
	}
	for(auto v:g[u]){
		if(v == p)continue;
		dfs1(v,u);
	}
}
int main()
{
	init();
	cin>>n;
	int u,v;
	rep(i , 1 , n ){
		cin>>u>>v;
		g[u].pb(v);
		g[v].pb(u);
	}
	dfs(1,0);
	ans[1] = dp[1];
	dfs1(1,0);
	rep(i , 1 , n + 1)
		cout<<ans[i]<<"\n";
	return 0;
}

