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;

#define INF 987654321
#define ll long long
#define MOD 1000000007

int N;
vector<int> g[200201];
ll fa[200201], dp[200201], up[200201];
int sub[200201], usub[200201];

ll pw(ll a, ll n)
{
	ll ret = 1;
	while(n)
	{
		if (n&1) ret=ret*a%MOD;
		a=a*a%MOD;
		n>>=1;
	}
	return ret;
}

ll inv(ll a)
{
	return pw(a, MOD-2);
}

ll C(int n, int r)
{
	return fa[n]*inv(fa[r])%MOD*inv(fa[n-r])%MOD;
}

void DFS(int n, int prev)
{
	sub[n] = 1;
	for(auto next : g[n])
	{
		if (next == prev) continue;
		DFS(next, n);
		sub[n] += sub[next];
	}

	// cal dp
	int sz = sub[n] - 1;
	dp[n] = 1;
	for(auto next : g[n])
	{
		if (next == prev) continue;
		dp[n] *= dp[next]; dp[n] %= MOD;
		dp[n] *= C(sz, sub[next]); dp[n] %= MOD;
		sz -= sub[next];
	}
}

void DFS2(int n, int prev)
{
	// cal usub
	usub[n] = 1;
	if (prev != 0)
	{
		usub[n] += usub[prev];
		usub[n] += sub[prev]-1-sub[n];
	}

	// cal up
	if (prev == 0) up[n] = 1;
	else
	{
		up[n] = up[prev]*dp[prev]%MOD*inv(dp[n])%MOD*inv(C(sub[prev]-1,sub[n]))%MOD;
		up[n] *= C(usub[n]-2, usub[prev]-1);
		up[n] %= MOD;
	}
	for(auto next : g[n])
	{
		if (next == prev) continue;
		DFS2(next, n);
	}
}

int main()
{
	fa[0] = 1;
	for(int i=1; i<200201; i++)
		fa[i] = fa[i-1] * i % MOD;
	scanf("%d", &N);
	for(int i=0; i<N-1; i++)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
	DFS(1, 0);
	DFS2(1, 0);
	for(int i=1; i<=N; i++)
	{
		ll res = dp[i]*up[i]%MOD*C(N-1, sub[i]-1)%MOD;
		printf("%lld\n", res);
	}
	return 0;
}