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 m 1000000007
#define r(i,n) for(l i=0;i<n;i++)
#define B push_back
using namespace std;
typedef long l;
typedef vector<l> L;

vector<L> p;

l P(l i, l b) {
	l a = 1;
	r(n, 62) {
		if ((b >> n) % 2 == 1) {
			a *= p[i][n];
			a %= m;
		}
	}
	return a;
}
int main() {
	deque<l> q;
	l N;cin >> N;
	l M = N - 1;
	L V,A(N, 0),a(N, -1),D(N, 1),J(N, 0),n(N, 1);
	vector<L> T(N);
	r(i, N * 2) {
		L w;
		w.B(i);
		r(j, 62)
			w.B((w[j] * w[j]) % m);
		p.B(w);
	}
	r(i, M) {
		l X, Y;
		cin >> X >> Y;
		X--; Y--;
		T[X].B(Y);
		T[Y].B(X);
		A[X]++;
		A[Y]++;
	}
	q.B(0);
	J[0] = 1;
	V.B(0);
	while (!q.empty()) {
		l x = q.front();
		q.pop_front();
		r(i, A[x]) {
			l E = T[x][i];
			if (!J[E]) {
				J[E] = 1;
				q.B(E);
				a[E] = x;
				V.B(E);
			}
		}
	}
	r(j, N) {
		l i = N - 1 - j,x = V[i];
		r(j, A[x]) {
			l E = T[x][j];
			if (E == a[x])
				continue;
			D[x] += D[E];
		}
	}
	r(i, N)
		n[0] = ((n[0]*(i + 1) % m)*P(D[i], m - 2))% m;
	r(j, N - 1) {
		l x = V[j + 1];
		n[x] = (((n[a[x]] * D[x]) % m) * P(N - D[x], m - 2)) % m;
	}
	r(i, N)
		cout << n[i] << "\n";
}