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
#import<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long LL;
typedef struct{int x;int y;int d;LL u;}H;
LL i,j,k,n,o=1e9+7,s,sz,f[200040]={1},pv[200040],vf[200040],w[200040],z[200040];
H c,e[400005];
int C(H a,H b){return a.x<b.x;}
LL P(LL x,LL y)
{
	LL i=o-2,v=x;
	for(;i;i>>=1)
	{
		if(i&1)
		{
			v=v*y%o;
		}
		y=y*y%o;
	}
	return v;
}
H dfs(LL g,LL r,LL v)
{
	LL m=1,t=0;
	H c;
	for(int i=pv[v];i<pv[v+1];i++)
	{
		if(e[i].y^g)
		{
			if(e[i].d)
			{
				m=m*e[i].u%o*P(P(f[t+e[i].d],f[t]),f[e[i].d])%o;
				t+=e[i].d;
			}
			else
			{
				c=dfs(v,i,e[i].y);
				m=m*c.u%o*P(P(f[t+c.d],f[t]),f[c.d])%o;
				t+=c.d;
			}
		}
	}
	e[r].d=c.d=++t;
	e[r].u=c.u=m;
	return c;
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(;i<n-1;i++)
	{
		cin>>e[i].x>>e[i].y;
		e[i+n-1].x=e[i].y;
		e[i+n-1].y=e[i].x;
		w[e[i].x]++;
		w[e[i].y]++;
		e[i].u=e[i+n-1].u=1;
	}
	sz=2*n-2;
	sort(e,e+sz,C);
	for(i=0;++i<sz;)
	{
		if(e[i].x>e[i-1].x)
		{
			for(j=e[i-1].x;j++<e[i].x;)
			{
				pv[j]=i;
			}
		}
	}
	for(j=e[sz-1].x;j++<n+1;)pv[j]=sz;
	for(i=0;i++<n;)
	{
		f[i]=f[i-1]*i%o;
	}
	for(i=0;i++<n;)
	{
		if(w[i]<2&&vf[e[pv[i]].y])z[i]=vf[e[pv[i]].y];
		else
		{
			c=dfs(0,sz,i);
			z[i]=c.u;
			if(w[i]<2)vf[e[pv[i]].y]=c.u;
		}
	}
	for(i=0;i++<n;)cout<<z[i]<<endl;
}