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;
const int N=2e5+10;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
int head[N],cnt=0,siz[N],n;
ll inv[N],pp[N];
ll dp[N];
ll ans[N];
struct edge{
    int next,to;
}e[N<<1];
void add(int u,int v){
    e[++cnt].next=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
ll pow(ll a, ll n, ll p)
{
    ll ans = 1;
    while(n)
    {
        if(n & 1) ans = ans * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return ans;
}
void init(){
    inv[1]=inv[0]=1;
    for(int i=2;i<=2e5;i++)inv[i]=inv[i-1]*pow(i,mod-2,mod)%mod;
    pp[0]=pp[1]=1;
    for(int i=2;i<=2e5;i++)pp[i]=pp[i-1]*i%mod;

}
ll cal(int n,int m){
    return pp[m]*inv[n]%mod*inv[m-n]%mod;
}
void dfs(int u,int fa){
    siz[u]=1;
    dp[u]=1;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa)continue;
        dfs(v,u);
        dp[u]=dp[u]*dp[v]%mod*cal(siz[v],siz[u]+siz[v]-1)%mod;
        siz[u]+=siz[v];
    }
}
void dfs1(int u,int fa){
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa)continue;
        dp[v]=dp[u]*pow(cal(siz[v],siz[u]-1),mod-2,mod)%mod*cal(siz[u]-siz[v],siz[u]-1)%mod;
        siz[v]=n;
        dfs1(v,u);
    }
}
int main()
{
    init();
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int a,b;
        scanf("%d %d",&a,&b);
        add(a,b);add(b,a);
    }
    dfs(1,0);
    dfs1(1,0);
    for(int i=1;i<=n;i++)printf("%lld\n",dp[i]);
    return 0;
}
