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

#define MAX 5002

int n;

vector<int> v[MAX];

int dp[MAX];
int p[MAX];
int mx[MAX];

inline void dfs(int b, int pr = -1) {
	p[b] = pr;
	dp[b] = 0;
	dp[b] = 1;
	mx[b] = 1;
	for (int go : v[b]) {
		if (go == pr)continue;
		dfs(go, b);
		dp[b] += dp[go];
		mx[b] = max(mx[b], dp[go]);
	}
	mx[b] = max(mx[b], n - dp[b]);
}
#define MOD 1000000007
vector<int> vv;

long long int d[MAX][MAX];

long long int c[MAX][MAX];
long long int k[MAX];

long long int W[MAX];

long long int ppow(long long int i, long long int j) {
	long long int r = 1;
	while (j) {
		if(j&1LL)r *= i;
		if (r >= MOD)r %= MOD;
		i *= i;
		i %= MOD;
		j >>= 1LL;
	}
	return r;
}
long long int inv[MAX];
long long int P(int a, int b) {
	long long int u = k[a];
	u *= inv[a - b];
	if (u >= MOD)u %= MOD;
	return u;
}
int main() {
	k[0] = 1;
	inv[0] = 1;
	for (int i = 1; i < MAX; i++) {
		k[i] = k[i - 1];
		k[i] *= i;
		if (k[i] >= MOD)k[i] %= MOD;
		inv[i] = ppow(k[i], MOD - 2);
	}
	c[0][0] = 1;
	for (int i = 0; i + 1 < MAX; i++) {
		for (int j = 0; j <= i; j++) {
			c[i + 1][j] += c[i][j];
			c[i + 1][j + 1] += c[i][j];
			if (c[i + 1][j] >= MOD)c[i + 1][j] %= MOD;
			if (c[i + 1][j + 1] >= MOD)c[i + 1][j + 1] %= MOD;
		}
	}
	cin >> n;
	for (int i = 1; i < n; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		a--;
		b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(0);
	bool flag = false;
	for (int i = 0; i < n; i++) {
		if (mx[i]*2<=n) {
			flag = true;
		}
	}
	if (flag==false) {
		long long int m = n / 2;
		long long int ans = 1;
		for (int i = 1; i <= m; i++) {
			ans *= i;
			if (ans >= MOD)ans %= MOD;
		}
		ans *= ans;
		ans %= MOD;
		ans = MOD - ans;
		ans += k[n];
		ans %= MOD;
		printf("%lld\n", ans);
	//	return 0;
	}
	int r = -1;
	for (int i = 0; i < n; i++) {
		if (mx[i] * 2 <= n) {
			r = i;
		}
	}
	for (int go : v[r]) {
		if (go != p[r]) {
			vv.push_back(dp[go]);
		}
	}
	if (p[r] != -1) {
		vv.push_back(n - dp[r]);
	}
	sort(vv.begin(), vv.end());
	d[0][0] = 1;
	for (int i = 0; i < vv.size(); i++) {
		for (int j = 0; j <= n; j++) {
			if (d[i][j] == 0)continue;
			for (int k = 0; k <= vv[i]; k++) {
				long long int U = d[i][j] * c[vv[i]][k];
				if (U >= MOD)U %= MOD;
				U *= P(vv[i], k);
				if (U >= MOD)U %= MOD;
				d[i + 1][j + k] += U;
				if (d[i + 1][j + k] >= MOD)d[i + 1][j + k] %= MOD;
			}
		}
	}
	long long int way = k[n];
	for (int j = 1; j <= n; j++) {
		long long int B = d[vv.size()][j];
		B *= k[n - j];
		B %= MOD;
		if (j % 2) {
			B = MOD - B;
		}
		way += B;
		way %= MOD;
	}
	printf("%lld\n", way);
	return 0;
	W[n-1] = 1;
	for (int i = n - 2; i >= 1; i--) {
		long long int tmp = d[vv.size()][i]*k[n-i];
		for (int j = i + 1; j <= n; j++) {
			long long int tmpp = W[j] * c[j][i];
			tmpp %= MOD;
			tmpp = MOD - tmpp;
			tmp += tmpp;
			tmp %= MOD;
		}
		W[i] = tmp;
	}
	long long int sum = 0;
	for (int i = 0; i <= n; i++) {
		sum += W[i];
		sum %= MOD;
	}
	sum = MOD - sum;
	sum += k[n];
	sum %= MOD;
	printf("%lld\n", sum);
	return 0;
}
### Prompt

Construct a Cpp code solution to the problem outlined:

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;

#define MAX 5002

int n;

vector<int> v[MAX];

int dp[MAX];
int p[MAX];
int mx[MAX];

inline void dfs(int b, int pr = -1) {
	p[b] = pr;
	dp[b] = 0;
	dp[b] = 1;
	mx[b] = 1;
	for (int go : v[b]) {
		if (go == pr)continue;
		dfs(go, b);
		dp[b] += dp[go];
		mx[b] = max(mx[b], dp[go]);
	}
	mx[b] = max(mx[b], n - dp[b]);
}
#define MOD 1000000007
vector<int> vv;

long long int d[MAX][MAX];

long long int c[MAX][MAX];
long long int k[MAX];

long long int W[MAX];

long long int ppow(long long int i, long long int j) {
	long long int r = 1;
	while (j) {
		if(j&1LL)r *= i;
		if (r >= MOD)r %= MOD;
		i *= i;
		i %= MOD;
		j >>= 1LL;
	}
	return r;
}
long long int inv[MAX];
long long int P(int a, int b) {
	long long int u = k[a];
	u *= inv[a - b];
	if (u >= MOD)u %= MOD;
	return u;
}
int main() {
	k[0] = 1;
	inv[0] = 1;
	for (int i = 1; i < MAX; i++) {
		k[i] = k[i - 1];
		k[i] *= i;
		if (k[i] >= MOD)k[i] %= MOD;
		inv[i] = ppow(k[i], MOD - 2);
	}
	c[0][0] = 1;
	for (int i = 0; i + 1 < MAX; i++) {
		for (int j = 0; j <= i; j++) {
			c[i + 1][j] += c[i][j];
			c[i + 1][j + 1] += c[i][j];
			if (c[i + 1][j] >= MOD)c[i + 1][j] %= MOD;
			if (c[i + 1][j + 1] >= MOD)c[i + 1][j + 1] %= MOD;
		}
	}
	cin >> n;
	for (int i = 1; i < n; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		a--;
		b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(0);
	bool flag = false;
	for (int i = 0; i < n; i++) {
		if (mx[i]*2<=n) {
			flag = true;
		}
	}
	if (flag==false) {
		long long int m = n / 2;
		long long int ans = 1;
		for (int i = 1; i <= m; i++) {
			ans *= i;
			if (ans >= MOD)ans %= MOD;
		}
		ans *= ans;
		ans %= MOD;
		ans = MOD - ans;
		ans += k[n];
		ans %= MOD;
		printf("%lld\n", ans);
	//	return 0;
	}
	int r = -1;
	for (int i = 0; i < n; i++) {
		if (mx[i] * 2 <= n) {
			r = i;
		}
	}
	for (int go : v[r]) {
		if (go != p[r]) {
			vv.push_back(dp[go]);
		}
	}
	if (p[r] != -1) {
		vv.push_back(n - dp[r]);
	}
	sort(vv.begin(), vv.end());
	d[0][0] = 1;
	for (int i = 0; i < vv.size(); i++) {
		for (int j = 0; j <= n; j++) {
			if (d[i][j] == 0)continue;
			for (int k = 0; k <= vv[i]; k++) {
				long long int U = d[i][j] * c[vv[i]][k];
				if (U >= MOD)U %= MOD;
				U *= P(vv[i], k);
				if (U >= MOD)U %= MOD;
				d[i + 1][j + k] += U;
				if (d[i + 1][j + k] >= MOD)d[i + 1][j + k] %= MOD;
			}
		}
	}
	long long int way = k[n];
	for (int j = 1; j <= n; j++) {
		long long int B = d[vv.size()][j];
		B *= k[n - j];
		B %= MOD;
		if (j % 2) {
			B = MOD - B;
		}
		way += B;
		way %= MOD;
	}
	printf("%lld\n", way);
	return 0;
	W[n-1] = 1;
	for (int i = n - 2; i >= 1; i--) {
		long long int tmp = d[vv.size()][i]*k[n-i];
		for (int j = i + 1; j <= n; j++) {
			long long int tmpp = W[j] * c[j][i];
			tmpp %= MOD;
			tmpp = MOD - tmpp;
			tmp += tmpp;
			tmp %= MOD;
		}
		W[i] = tmp;
	}
	long long int sum = 0;
	for (int i = 0; i <= n; i++) {
		sum += W[i];
		sum %= MOD;
	}
	sum = MOD - sum;
	sum += k[n];
	sum %= MOD;
	printf("%lld\n", sum);
	return 0;
}
```