#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5005;
const int MOD = 1e9 + 7;

int N;
vector <int> E[MAXN];
int fact[MAXN], choose[MAXN][MAXN];
int sz[MAXN];
int centroid;
int mini = MAXN;
int dp[MAXN][MAXN];

void load() {
	scanf("%d", &N);
	for (int i = 1; i < N; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		E[x].push_back(y);
		E[y].push_back(x);
	}
}

inline int add(int x, int y) {
	x += y;
	if (x >= MOD)
		x -= MOD;
	else if (x < 0)
		x += MOD;
	return x;
}

inline int mul(int x, int y) {
	return (long long)x * y % MOD;
}

void init() {
	fact[0] = 1;
	for (int i = 1; i < MAXN; i++)
		fact[i] = mul(fact[i - 1], i);
	
	choose[0][0] = 1;
	for (int i = 1; i < MAXN; i++) {
		choose[i][0] = 1;
		for (int j = 1; j <= i; j++)
			choose[i][j] = add(choose[i - 1][j], choose[i - 1][j - 1]);
	}
}

void dfs(int x, int p) {
	sz[x] = 1;
	int mx = 0;
	for (auto it : E[x])
		if (it != p) {
			dfs(it, x);
			mx = max(mx, sz[it]);
			sz[x] += sz[it];
		}
	mx = max(mx, N - sz[x]);
	if (mx < mini) {
		mini = mx;
		centroid = x;
	}
}

int go(int x, int p) {
	int res = 1;
	for (auto it : E[x])
		if (it != p)
			res += go(it, x);
	return res;
}

int solve() {
	dfs(1, 0);
			
	vector <int> a;
	a.push_back(0);
	for (auto it : E[centroid]) 
		a.push_back(go(it, centroid));
	
	int K = a.size();
	dp[0][0] = 1;
	for (int i = 1; i < K; i++) 
		for (int j = 0; j < N; j++)
			for (int k = 0; k <= a[i] && k <= j; k++) 
				dp[i][j] = add(dp[i][j], mul(dp[i - 1][j - k], mul(mul(choose[a[i]][k], choose[a[i]][k]), fact[k])));
	
	int sol = 0;
	for (int i = 0; i < N; i++) {
		int tmp = mul(fact[N - i], dp[K - 1][i]);
		sol = add(sol, i % 2 ? -tmp : tmp);
	}
	
	return sol;
}

int main() {
	init();
	load();
	printf("%d\n", solve());
	return 0;
}
### Prompt

Your task is to create a Cpp solution 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 <bits/stdc++.h>
using namespace std;

const int MAXN = 5005;
const int MOD = 1e9 + 7;

int N;
vector <int> E[MAXN];
int fact[MAXN], choose[MAXN][MAXN];
int sz[MAXN];
int centroid;
int mini = MAXN;
int dp[MAXN][MAXN];

void load() {
	scanf("%d", &N);
	for (int i = 1; i < N; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		E[x].push_back(y);
		E[y].push_back(x);
	}
}

inline int add(int x, int y) {
	x += y;
	if (x >= MOD)
		x -= MOD;
	else if (x < 0)
		x += MOD;
	return x;
}

inline int mul(int x, int y) {
	return (long long)x * y % MOD;
}

void init() {
	fact[0] = 1;
	for (int i = 1; i < MAXN; i++)
		fact[i] = mul(fact[i - 1], i);
	
	choose[0][0] = 1;
	for (int i = 1; i < MAXN; i++) {
		choose[i][0] = 1;
		for (int j = 1; j <= i; j++)
			choose[i][j] = add(choose[i - 1][j], choose[i - 1][j - 1]);
	}
}

void dfs(int x, int p) {
	sz[x] = 1;
	int mx = 0;
	for (auto it : E[x])
		if (it != p) {
			dfs(it, x);
			mx = max(mx, sz[it]);
			sz[x] += sz[it];
		}
	mx = max(mx, N - sz[x]);
	if (mx < mini) {
		mini = mx;
		centroid = x;
	}
}

int go(int x, int p) {
	int res = 1;
	for (auto it : E[x])
		if (it != p)
			res += go(it, x);
	return res;
}

int solve() {
	dfs(1, 0);
			
	vector <int> a;
	a.push_back(0);
	for (auto it : E[centroid]) 
		a.push_back(go(it, centroid));
	
	int K = a.size();
	dp[0][0] = 1;
	for (int i = 1; i < K; i++) 
		for (int j = 0; j < N; j++)
			for (int k = 0; k <= a[i] && k <= j; k++) 
				dp[i][j] = add(dp[i][j], mul(dp[i - 1][j - k], mul(mul(choose[a[i]][k], choose[a[i]][k]), fact[k])));
	
	int sol = 0;
	for (int i = 0; i < N; i++) {
		int tmp = mul(fact[N - i], dp[K - 1][i]);
		sol = add(sol, i % 2 ? -tmp : tmp);
	}
	
	return sol;
}

int main() {
	init();
	load();
	printf("%d\n", solve());
	return 0;
}
```