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;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=5e15;

const ll N=2e5+10;
vector<map<ll,ll>> si(N),dp(N);
vector<set<ll>> G(N);
ll n;

ll mpow(ll x, ll n) {
  ll ans=1;
  while(n>0) {
    if(n&1) {
      ans=ans*x%mod;
    }
    x=x*x%mod;
    n>>=1;
  }
  return ans;
}

vector<ll> tfact(1e7+1);
void fact(ll n) {
  for(ll i=0;i<=n;i++) {
    if(i==0) {
      tfact[i]=1;
    }
    else {
      tfact[i]=tfact[i-1]*i%mod;
    }
  }
}

ll dfs1(ll f, ll ff) {
  if(si[f][ff]) return si[f][ff];
  ll res=0;
  for(auto p:G[f]) {
    if(p==ff) continue;
    res+=dfs1(p,f);
  }
  if(ff) si[ff][f]=n-res-1;
  return si[f][ff]=res+1;
}

ll dfs2(ll f,ll ff) {
  if(dp[f][ff]) return dp[f][ff];
  ll res=1;
  if(dp[f][0]) {
    res=dp[f][0];
    (res*=mpow(dfs2(ff,f),mod-2)*tfact[dfs1(ff,f)]%mod)%=mod;
    (res*=mpow(tfact[dfs1(f,0)-1],mod-2))%=mod;
  }
  else {
    for(auto p:G[f]) {
      if(p==ff) continue;
      (res*=dfs2(p,f)*mpow(tfact[dfs1(p,f)],mod-2)%mod)%=mod;
    }
  }
  (res*=tfact[dfs1(f,ff)-1])%=mod;
  return dp[f][ff]=res;
}

void bfs(ll f) {
  queue<ll> q;
  q.push(f);
  while(q.size()) {
    ll n=q.front();
    q.pop();
    dfs2(n,0);
    for(auto p:G[n]) {
      if(dp[p][0]) continue;
      q.push(p);
    }
  }
}

int main() {
  cin >> n;
  for(ll i=0;i<n-1;i++) {
    ll a,b;
    cin >> a >> b;
    G[a].insert(b);
    G[b].insert(a);
  }
  fact(N);
  bfs(1);
  for(ll i=1;i<=n;i++) {
    cout << dfs2(i,0) << endl;
  }
}