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
// i hope i get better                                                           
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int sz=2e5+9;
int n;
int a,b;
vector<int> v[sz];
bool visited[sz];
ll s[sz];
ll m=1e9+7;
ll add(ll a,ll b){return (a%m+b%m)%m;}
ll mul(ll a,ll b){return (a%m*b%m)%m;}
ll f[sz];
ll dp[sz];

ll modpow(ll b,ll p){
	if(!b) return 0;
	if(!p) return 1;
	ll u=modpow(b,p>>1);
	u=mul(u,u);
	if(p&1) u=mul(u,b);
	return u;
}

ll c(int N,int K){
	ll num=f[N];
	ll den=mul(f[K],f[N-K]);
	den=modpow(den,m-2);
	return mul(num,den);
}

void dfs(int i,int p=1){
	visited[i]=1;
	dp[i]=1;
	for(auto u:v[i]){
		if(u==p||visited[u]) continue;
		dfs(u,i);
		s[i]+=s[u];
		dp[i]=mul(dp[i],dp[u]);
		dp[i]=mul(dp[i],c(s[i],s[u]));
	}
	s[i]++;
}

void solve(int i,int p=1){
	visited[i]=1;
	ll dpi;
	for(int u:v[i]){
		if(u==p||visited[u]) continue;
		dpi=mul(dp[i],modpow(dp[u],m-2));
		s[i]--;
		dpi=mul(dpi,modpow(c(s[i],s[u]),m-2));
		s[i]-=s[u];
		s[i]++;
		s[u]+=s[i]-1;
		dp[u]=mul(dp[u],dpi);
		dp[u]=mul(dp[u],c(s[u],s[i]));
		s[u]++;
		solve(u,i);
		s[u]--;
		s[u]-=s[i];
		s[u]++;
		s[i]+=s[u];
	}
}

int main(){
	scanf("%d",&n);
	f[0]=f[1]=1;
	for(int i=2;i<=n;i++) f[i]=mul(i,f[i-1]);
	for(int i=0;i<n-1;i++){
		scanf("%d %d",&a,&b);
		v[a].pb(b);
		v[b].pb(a);
	}
	dfs(1);
	memset(visited,0,sizeof(visited));
	solve(1);
	for(int i=1;i<=n;i++) printf("%lld\n",dp[i]);
	// for(int i=1;i<=n;i++) printf("%d\n",s[i]);
    return 0;
}