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 int long long
const int MOD=1e9+7;

vector< int > g[200000];
int dist[200000], ans[200000],son[200000],anc[200000],pre[200000];
int F[200000];

void dfs1(int idx, int par)
{
  for(int &to : g[idx]) {
    if(to == par) continue;
    dfs1(to, idx);
    son[idx]++;
  }
}
void dfs3(int idx,int par){
  for(int &to:g[idx]){
    if(to==par)continue;
    dfs3(to,idx);
    anc[idx]+=1+anc[to];
  }
}
int pw(int n,int k){
  assert(k>=0);
  int res=1;
  while(k){
    if(k&1)(res*=n)%=MOD;
    (n*=n)%=MOD;
    k>>=1;
  }
  return res;
}
void dfs4(int idx,int par){
  for(int &to:g[idx]){
    if(to==par)continue;
    dfs4(to,idx);
    (pre[idx]*=pre[to]*(anc[to]+1)%MOD)%=MOD;
  }
}


void dfs2(int idx,int par)
{
  ans[idx]=dist[idx];
  for(int &to : g[idx]) {
    if(to == par) continue;
    int tmp=pre[idx];
    (tmp*=pw(pre[to]*(anc[to]+1)%MOD,MOD-2))%=MOD;
    int tmpa=anc[idx];
    tmpa-=anc[to]+1;tmp+=MOD;
    (pre[to]*=(tmp*(tmpa+1))%MOD)%=MOD;
    anc[to]+=1+tmpa;
    dist[to]=F[anc[to]]*pw(pre[to],MOD-2)%MOD;
    dfs2(to,idx);
  }
}

signed main()
{
  int N;
  cin >> N;
  for(int i = 0; i < N - 1; i++) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  F[0]=1;
  for(int i=1;i<200000;i++)F[i]=(F[i-1]*i)%MOD;
  for(int i=0;i<N;i++)pre[i]=1;

  dfs1(0, -1);
  dfs3(0,-1);
  dfs4(0,-1);
  for(int i=0;i<N;i++)dist[i]=F[anc[i]]*pw(pre[i],MOD-2)%MOD;
  dfs2(0, -1);
  for(int i = 0; i < N; i++) {
    cout<<ans[i]<<endl;
  }
}
