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<cstdio>
#include<string>
#include<cstring>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<bitset>
#include<iostream>
#include<algorithm>
#include<numeric>
#include<complex>
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define ll long long
#define pii pair<int,int> 
const int N=1e6+10;
const int mod=1e9+7;
using namespace std;

int f[N],inv[N];
ll ksm(ll a, ll k){
    ll ans=1;
    while(k){if(k&1) ans=ans*a%mod; a=a*a%mod; k>>=1;}
    return ans;
}
void init(int n){
    f[0]=1; inv[0]=1;
    for(int i=1;i<=n;++i) f[i]=1LL*f[i-1]*i%mod,inv[i]=ksm(f[i],mod-2);
}
vector<int> v[N];
int n,dp[N],sz[N],ans[N];
void dfs(int x, int fa=-1){
    sz[x]=1; dp[x]=1;
    for(auto e: v[x]) if(e!=fa){
        dfs(e,x);
        sz[x]+=sz[e];
        dp[x]=1LL*dp[x]*dp[e]%mod*inv[sz[e]]%mod;
    }
    dp[x]=1LL*dp[x]*f[sz[x]-1]%mod;
}
void dfs2(int x, int fa=-1){
    ans[x]=dp[x];
    ll tmp=dp[x];
    for(auto e: v[x]) if(e!=fa){
        ll ff=1LL*tmp*ksm(dp[e],mod-2)%mod*inv[n-1]%mod*f[sz[e]]%mod*f[n-1-sz[e]]%mod;
        dp[e]=ff*dp[e]%mod*inv[sz[e]-1]%mod*f[n-1]%mod*inv[n-sz[e]]%mod; 
        dp[x]=ff;
        dfs2(e,x);
    }
}
void solve(){
    scanf("%d",&n);
    init(n);
    for(int i=1,x,y;i<n;++i){
        scanf("%d%d",&x,&y);
        v[x].pb(y);
        v[y].pb(x);
    }
    dfs(1);
    dfs2(1);
    for(int i=1;i<=n;++i) printf("%d\n",ans[i]);
}
int main() 
{
    int _=1;  //scanf("%d",&_);
    while(_--) solve();
return 0;
}
/*
2 1
1 2
*/


