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 <iostream>
#include <vector>
using namespace std;
using ll = long long;
vector<int> G[200010];
long long mod = 1000000007;
const int MX = 200010;
ll f[MX],inv[MX],fi[MX];
ll pw(ll a,ll x){
    ll ret = 1;
    while(x){
        if(x&1){
            (ret *= a) %= mod; x--;
        }
        (a *= a) %= mod; x /= 2;
    }
    return ret;
}
ll inverse(ll x){
    return pw(x,mod - 2);
}

void solve(){
    ll i;
    f[0] = 1; fi[0] = 1;
    for(i=1;i<MX;i++) f[i] = f[i - 1]*i%mod;
    fi[MX - 1] = inverse(f[MX - 1]);
    for(i=MX - 2;i>=1;i--) fi[i] = fi[i + 1]*(i + 1)%mod;
    for(i=1;i<MX;i++) inv[i] = f[i]*fi[i - 1]%mod;
}

ll ans[200010],dp[200010],sz[200010];
ll dfs(int s,int p){
    ll ret = 1,val = 1;
    for(int v:G[s]){
        if(v==p) continue;
        ll x = dfs(v,s);
        (val *= dp[v]) %= mod; (val *= fi[x]) %= mod;
        ret += x;
    }
    (val *= f[ret - 1]) %= mod;
    dp[s] = val; sz[s] = ret;
    return ret;
}

int n;
void dfs1(int s,int p){
    ans[s] = dp[s];
    for(int v:G[s]){
        if(v==p) continue;
        ll x = dp[v],y = dp[s],s1 = sz[v],s2 = sz[s];
        sz[v] = n; sz[s] = n - s1;
        (dp[s] *= fi[n - 1]%mod*f[s1]%mod*inverse(x)%mod*f[sz[s] - 1]%mod) %= mod;
        (dp[v] *= f[n - 1]%mod*dp[s]%mod*fi[sz[s]]%mod*fi[s1 - 1]%mod) %= mod;
        dfs1(v,s);
        dp[v] = x; dp[s] = y; sz[v] = s1; sz[s] = s2;
    }
}

int main(){
    int i;
    cin >> n;
    for(i=0;i<n - 1;i++){
        int a,b; cin >> a >> b; a--; b--;
        G[a].push_back(b); G[b].push_back(a);
    }
    solve();
    dfs(0,-1); dfs1(0,-1);
    for(i=0;i<n;i++){
        cout << ans[i] << endl;
    }
}