#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
const int N = 5 * 1000 + 100;
const int MOD = 1000000007;
const int oo = 1e9;

int n, x, y, sz[N], dp[N][N];
ll fact[N], inv[N];
vector<int> g[N], cen, v;

ll fast(ll a , ll b) {
	if (!b)return 1ll;
	ll res = fast(a, b / 2);
	res = (res * res) % MOD;
	if (b & 1)
		return (res * a) % MOD;
	return res;
}
ll nCk(ll n , ll k) {
	return ((fact[n] * inv[n - k]) % MOD * inv[k]) % MOD;
}

void dfs(int u , int p) {
	sz[u] = 1;
	int mx = 1;
	vector<int> ar;
	for (int i = 0; i < g[u].size(); ++i) {
		int v = g[u][i];
		if (v == p)continue;
		dfs(v, u);
		ar.pb(sz[v]);
		sz[u] += sz[v];
		mx = max(mx, sz[v]);
	}
	if (n - sz[u] > 0)
		ar.pb(n - sz[u]);
	mx = max(mx, n - sz[u]);
	if (2 * mx <= n) {
		v = ar;
		cen.pb(u);
	}
}
int calc(int idx , int rem) {
	if (idx == v.size())return !rem;
	int &ret = dp[idx][rem];
	if (ret != -1)return ret;
	ret = 0;
	for (int take = 0; take <= min(rem, v[idx]); ++take) {
		ret = (ret + 1ll * (((nCk(v[idx], take) * nCk(v[idx], take)) % MOD) * fact[take])%MOD* calc(idx + 1, rem - take)) % MOD;
	}
	return ret;
}
int main() {
	
	memset(dp, -1, sizeof dp);
	scanf("%d", &n);
	for (int i = 0; i < n - 1; ++i) {
		scanf("%d%d", &x, &y);
		g[x].pb(y);
		g[y].pb(x);
	}
	fact[0] = 1;
	inv[0] = fast(fact[0], MOD - 2);
	for (int i = 1 ; i <=  n ; ++i) {
		fact[i] = (fact[i - 1] * i) % MOD;
		inv[i] = fast(fact[i], MOD - 2);
	}
	dfs(1, -1);
	if (cen.size() == 2) {
		printf("%lld\n", (fact[n / 2]*fact[n / 2]) % MOD );
		return 0;
	}

	ll res = 0;
	for (int i = 1; i <= n ; ++i) {
		res = (res + (i % 2 == 1 ? 1 : -1) * (calc(0, i) * fact[n - i])%MOD + MOD) % MOD;
                
	}
	res = (fact[n]-res+MOD)%MOD;
	cout << res << endl;

	return 0;
}
### Prompt

Please formulate 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>
#define pb push_back
#define mp make_pair
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
const int N = 5 * 1000 + 100;
const int MOD = 1000000007;
const int oo = 1e9;

int n, x, y, sz[N], dp[N][N];
ll fact[N], inv[N];
vector<int> g[N], cen, v;

ll fast(ll a , ll b) {
	if (!b)return 1ll;
	ll res = fast(a, b / 2);
	res = (res * res) % MOD;
	if (b & 1)
		return (res * a) % MOD;
	return res;
}
ll nCk(ll n , ll k) {
	return ((fact[n] * inv[n - k]) % MOD * inv[k]) % MOD;
}

void dfs(int u , int p) {
	sz[u] = 1;
	int mx = 1;
	vector<int> ar;
	for (int i = 0; i < g[u].size(); ++i) {
		int v = g[u][i];
		if (v == p)continue;
		dfs(v, u);
		ar.pb(sz[v]);
		sz[u] += sz[v];
		mx = max(mx, sz[v]);
	}
	if (n - sz[u] > 0)
		ar.pb(n - sz[u]);
	mx = max(mx, n - sz[u]);
	if (2 * mx <= n) {
		v = ar;
		cen.pb(u);
	}
}
int calc(int idx , int rem) {
	if (idx == v.size())return !rem;
	int &ret = dp[idx][rem];
	if (ret != -1)return ret;
	ret = 0;
	for (int take = 0; take <= min(rem, v[idx]); ++take) {
		ret = (ret + 1ll * (((nCk(v[idx], take) * nCk(v[idx], take)) % MOD) * fact[take])%MOD* calc(idx + 1, rem - take)) % MOD;
	}
	return ret;
}
int main() {
	
	memset(dp, -1, sizeof dp);
	scanf("%d", &n);
	for (int i = 0; i < n - 1; ++i) {
		scanf("%d%d", &x, &y);
		g[x].pb(y);
		g[y].pb(x);
	}
	fact[0] = 1;
	inv[0] = fast(fact[0], MOD - 2);
	for (int i = 1 ; i <=  n ; ++i) {
		fact[i] = (fact[i - 1] * i) % MOD;
		inv[i] = fast(fact[i], MOD - 2);
	}
	dfs(1, -1);
	if (cen.size() == 2) {
		printf("%lld\n", (fact[n / 2]*fact[n / 2]) % MOD );
		return 0;
	}

	ll res = 0;
	for (int i = 1; i <= n ; ++i) {
		res = (res + (i % 2 == 1 ? 1 : -1) * (calc(0, i) * fact[n - i])%MOD + MOD) % MOD;
                
	}
	res = (fact[n]-res+MOD)%MOD;
	cout << res << endl;

	return 0;
}
```