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>
#define MAX (ll)(2e5 + 7)
#define INF (ll)(1e17 + 7)
#define MOD (ll)(1e9 + 7)
#define PI (double)(3.14159265)
#define IO ios_base :: sync_with_stdio (false);
#define LOG 22

using namespace std;
using ll = long long;

vector<int> gr[MAX];
int dp[MAX], sub[MAX], f[MAX], n;

int mult (int a, int b) {
	return (a * 1LL * b) % MOD;
}

int add (int a, int b) {
	return (a + b) % MOD;
}

int pw (int a, int b) {
	int r = 1;
	while (b) {
		if (b & 1) {
			r = mult (r, a);
		}
		b >>= 1;
		a = mult (a, a);
	}
	return r;
}

void dfs (int node, int par) {
	sub[node] = dp[node] = 1;
	for (int x : gr[node]) {
		if (x != par) {
			dfs (x, node);
			sub[node] += sub[x];
			dp[node] = mult (dp[node], pw (f[sub[x]], MOD - 2));
			dp[node] = mult (dp[node], dp[x]);
		}
	}
	dp[node] = mult (dp[node], f[sub[node] - 1]);
}

void dfs (int node, int par, int ch) {
	dp[node] = mult (dp[node], mult (mult (f[n - 1], ch), pw (mult (f[sub[node] - 1], f[n - sub[node]]), MOD - 2)));
	for (int x : gr[node]) {
		if (x == par) {
			continue;
		}
		dfs (x, node, mult (dp[node], mult (mult (f[sub[x]], f[n - sub[x] - 1]), pw (mult (dp[x], f[n - 1]), MOD - 2))));
	}
}
	
int main () {
	cin >> n;
	f[0] = 1;
	for (int i = 1; i < MAX; i++) {
		f[i] = mult (f[i - 1], i);
	}
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		gr[u].push_back (v);
		gr[v].push_back (u);
	}
	dfs (1, 0);
	dfs (1, 0, 1);
	for (int i = 1; i <= n; i++) {
		cout << dp[i] << "\n";
	}
}
