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 <stdio.h>
#include <vector>
using namespace std;
typedef long long ll;
int N;
int cnt[200001];
int par[200001];
ll fact[200001]={1,};
ll inv[200001];
ll dp[200001];
ll rdp[200001];
vector<vector<int> > map;
const ll M = 1000000007;
ll modpow(ll a, ll n){
	ll ret = 1;
	for(int i=0;i<=30;i++){
		if(n&(1<<i)) ret=(a*ret)%M;
		a=(a*a)%M;
	}
	return ret;
}

int dfs(int x){
	cnt[x] = 1;
	for(int nx : map[x]){
		if(nx!=par[x]){
			par[nx] = x;
			cnt[x] += dfs(nx);
		}
	}
	return cnt[x];
}

ll sol(int x){
	if(dp[x]) return dp[x];
	ll ret = fact[cnt[x]-1];
	for(int nx : map[x]){
		if(nx!=par[x]){
			ret = (ret*sol(nx))%M;
			ret = (ret*inv[cnt[nx]])%M;
		}
	}
	return dp[x] = ret;
}
ll rsol(int x){
	if(rdp[x]) return rdp[x];
	ll ret = fact[N-1];
	for(int nx : map[x]){
		if(nx == par[x]){
			ll tmp[] = {rsol(nx),inv[N-1],fact[N-1-cnt[x]],fact[cnt[x]],modpow(sol(x),M-2),inv[N-cnt[x]]};
			for(int i=0;i<6;i++){
				ret *= tmp[i];
				ret %= M;
			}
		}
		else{
			ret = (ret*sol(nx))%M;
			ret = (ret*inv[cnt[nx]])%M;
		}
	}
	return rdp[x] = ret;
}
int main(){
	for(int i=1;i<=200000;i++) fact[i] = (fact[i-1]*i)%M;
	inv[200000] = modpow(fact[200000],M-2);
	for(int i=200000;i>0;i--) inv[i-1] = (inv[i]*i)%M;
	scanf("%d",&N);
	map.resize(N+1);
	for(int i=0;i<N-1;i++){
		int a,b;
		scanf("%d %d",&a,&b);
		map[a].push_back(b);
		map[b].push_back(a);
	}
	dfs(1);
	for(int i=1;i<=N;i++){
		printf("%lld\n",rsol(i));
	}
}