#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int n, C[5010], Mod = 1000000007;
vector<int>E[5010];
void DFS(int a, int pp) {
	int i;
	C[a] = 1;
	for (i = 0; i < E[a].size(); i++) {
		if (E[a][i] != pp) {
			DFS(E[a][i], a);
			C[a] += C[E[a][i]];
		}
	}
}
int D[5010][5010], F[5010], Comb[5010][5010];
int Calc(vector<int> &V) {
	int i, j, k, sz = V.size(), s = 0;
	D[0][0] = 1;
	for (i = 0;i<sz; i++) {
		int c = V[i];
		for (j = 0; j <= s + c; j++)D[i + 1][j] = 0;
		for (j = 0; j <= s; j++) {
			for (k = 0; k <= c; k++) {
				D[i + 1][j + k] = (D[i + 1][j + k] + 1ll * D[i][j] * Comb[c][k] % Mod * Comb[c][k] % Mod * F[k]) % Mod;
			}
		}
		s += c;
	}
	for (i = s; i >= 0; i--) {
		int r = 1ll * D[sz][i] * F[s - i] % Mod;
		for (j = i + 1; j <= s; j++) {
			r = (r - 1ll * D[sz][j] * Comb[j][i]%Mod+Mod) % Mod;
		}
		D[sz][i] = r;
	}
	return D[sz][0];
}
int main() {
	int i, a, b, j;
	scanf("%d", &n);
	F[0] = 1;
	for (i = 1; i <= n; i++)F[i] = 1ll * F[i - 1] * i%Mod;
	for (i = 0; i <= n; i++) {
		Comb[i][0] = 1;
		for (j = 1; j <= i; j++) {
			Comb[i][j] = (Comb[i - 1][j - 1] + Comb[i - 1][j]) % Mod;
		}
	}
	for (i = 1; i < n; i++) {
		scanf("%d%d", &a, &b);
		E[a].push_back(b);
		E[b].push_back(a);	
	}
	DFS(1, 0);
	int M = 1e9, pv = -1;
	for (i = 1; i <= n; i++) {
		if (C[i] * 2 >= n && M > C[i])M = C[i], pv = i;
	}
	if (M * 2 == n) {
		int res = 1;
		for (i = 1; i <= n / 2; i++) {
			res = 1ll * res*i*i%Mod;
		}
		printf("%d\n", res);
		return 0;
	}
	vector<int>V;
	for (i = 0; i < E[pv].size(); i++) {
		int t = C[E[pv][i]];
		if (t > M) t = n-M;
		V.push_back(t);
	}
	int s = Calc(V);
	V.push_back(1);
	printf("%d\n", (s + Calc(V)) % Mod);
}
### Prompt

Please create a solution in Cpp to the following problem:

There is a tree with N vertices. The vertices are numbered 1 through N. The i-th edge (1 \leq i \leq N - 1) connects Vertex x_i and y_i. For vertices v and w (1 \leq v, w \leq N), we will define the distance between v and w d(v, w) as "the number of edges contained in the path v-w".

A squirrel lives in each vertex of the tree. They are planning to move, as follows. First, they will freely choose a permutation of (1, 2, ..., N), p = (p_1, p_2, ..., p_N). Then, for each 1 \leq i \leq N, the squirrel that lived in Vertex i will move to Vertex p_i.

Since they like long travels, they have decided to maximize the total distance they traveled during the process. That is, they will choose p so that d(1, p_1) + d(2, p_2) + ... + d(N, p_N) will be maximized. How many such ways are there to choose p, modulo 10^9 + 7?

Constraints

* 2 \leq N \leq 5,000
* 1 \leq x_i, y_i \leq N
* The input graph is a tree.

Input

Input is given from Standard Input in the following format:


N
x_1 y_1
x_2 y_2
:
x_{N - 1} y_{N - 1}


Output

Print the number of the ways to choose p so that the condition is satisfied, modulo 10^9 + 7.

Examples

Input

3
1 2
2 3


Output

3


Input

4
1 2
1 3
1 4


Output

11


Input

6
1 2
1 3
1 4
2 5
2 6


Output

36


Input

7
1 2
6 3
4 5
1 7
1 5
2 3


Output

396

### Response

```cpp
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int n, C[5010], Mod = 1000000007;
vector<int>E[5010];
void DFS(int a, int pp) {
	int i;
	C[a] = 1;
	for (i = 0; i < E[a].size(); i++) {
		if (E[a][i] != pp) {
			DFS(E[a][i], a);
			C[a] += C[E[a][i]];
		}
	}
}
int D[5010][5010], F[5010], Comb[5010][5010];
int Calc(vector<int> &V) {
	int i, j, k, sz = V.size(), s = 0;
	D[0][0] = 1;
	for (i = 0;i<sz; i++) {
		int c = V[i];
		for (j = 0; j <= s + c; j++)D[i + 1][j] = 0;
		for (j = 0; j <= s; j++) {
			for (k = 0; k <= c; k++) {
				D[i + 1][j + k] = (D[i + 1][j + k] + 1ll * D[i][j] * Comb[c][k] % Mod * Comb[c][k] % Mod * F[k]) % Mod;
			}
		}
		s += c;
	}
	for (i = s; i >= 0; i--) {
		int r = 1ll * D[sz][i] * F[s - i] % Mod;
		for (j = i + 1; j <= s; j++) {
			r = (r - 1ll * D[sz][j] * Comb[j][i]%Mod+Mod) % Mod;
		}
		D[sz][i] = r;
	}
	return D[sz][0];
}
int main() {
	int i, a, b, j;
	scanf("%d", &n);
	F[0] = 1;
	for (i = 1; i <= n; i++)F[i] = 1ll * F[i - 1] * i%Mod;
	for (i = 0; i <= n; i++) {
		Comb[i][0] = 1;
		for (j = 1; j <= i; j++) {
			Comb[i][j] = (Comb[i - 1][j - 1] + Comb[i - 1][j]) % Mod;
		}
	}
	for (i = 1; i < n; i++) {
		scanf("%d%d", &a, &b);
		E[a].push_back(b);
		E[b].push_back(a);	
	}
	DFS(1, 0);
	int M = 1e9, pv = -1;
	for (i = 1; i <= n; i++) {
		if (C[i] * 2 >= n && M > C[i])M = C[i], pv = i;
	}
	if (M * 2 == n) {
		int res = 1;
		for (i = 1; i <= n / 2; i++) {
			res = 1ll * res*i*i%Mod;
		}
		printf("%d\n", res);
		return 0;
	}
	vector<int>V;
	for (i = 0; i < E[pv].size(); i++) {
		int t = C[E[pv][i]];
		if (t > M) t = n-M;
		V.push_back(t);
	}
	int s = Calc(V);
	V.push_back(1);
	printf("%d\n", (s + Calc(V)) % Mod);
}
```