#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

const int N = 5e3 + 10;
const int mod = 1e9 + 7;

int qpow(int a, int b) {
	int ret = 1;
	while (b) {
		if (b & 1) ret = 1ll * ret * a % mod;
		a = 1ll * a * a % mod, b >>= 1;
	}
	return ret;
}

int n, fac[N], ifac[N], f[N], nf[N], siz[N], g[N], mn = 1e9;
vector<int> E[N];

void dfs(int u, int fa) {
	siz[u] = 1;
	for (auto v : E[u])
		if (v ^ fa) {
			dfs(v, u), siz[u] += siz[v];
			g[u] = max(g[u], siz[v]);
		}
	g[u] = max(g[u], n - siz[u]);
	mn = min(mn, g[u]);
}

int main() {
	cin >> n;
	for (int i = 1, u, v; i < n; i++) cin >> u >> v, E[u].push_back(v), E[v].push_back(u);
	fac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
	ifac[n] = qpow(fac[n], mod - 2);
	for (int i = n; i; i--) ifac[i - 1] = 1ll * ifac[i] * i % mod;
	dfs(1, 0);
	int x = 0, y = 0;
	for (int i = 1; i <= n; i++)
		if (g[i] == mn) (x ? y : x) = i;
	if (y) cout << 1ll * fac[n / 2] * fac[n / 2] % mod;
	else {
		f[0] = 1; int sum = 0, ans = 0;
		for (auto u : E[x]) {
			dfs(u, x); memset(nf, 0, sizeof(nf));
			for (int i = 0; i <= sum; i++)
				for (int j = 0; j <= siz[u]; j++)
					nf[i + j] = (nf[i + j] + 1ll * f[i] * fac[siz[u]] % mod * fac[siz[u]] % mod * ifac[j] % mod * ifac[siz[u] - j] % mod * ifac[siz[u] - j]) % mod;
			swap(f, nf); sum += siz[u];
		}
		for (int i = 0; i < n; i++) ans = (ans + 1ll * f[i] * ((i & 1) ? mod - 1 : 1) % mod * fac[n - i]) % mod;
		cout << ans;
	}
	return 0;
}
### Prompt

Create a solution in CPP for 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<iostream>
#include<vector>
#include<cstring>
using namespace std;

const int N = 5e3 + 10;
const int mod = 1e9 + 7;

int qpow(int a, int b) {
	int ret = 1;
	while (b) {
		if (b & 1) ret = 1ll * ret * a % mod;
		a = 1ll * a * a % mod, b >>= 1;
	}
	return ret;
}

int n, fac[N], ifac[N], f[N], nf[N], siz[N], g[N], mn = 1e9;
vector<int> E[N];

void dfs(int u, int fa) {
	siz[u] = 1;
	for (auto v : E[u])
		if (v ^ fa) {
			dfs(v, u), siz[u] += siz[v];
			g[u] = max(g[u], siz[v]);
		}
	g[u] = max(g[u], n - siz[u]);
	mn = min(mn, g[u]);
}

int main() {
	cin >> n;
	for (int i = 1, u, v; i < n; i++) cin >> u >> v, E[u].push_back(v), E[v].push_back(u);
	fac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
	ifac[n] = qpow(fac[n], mod - 2);
	for (int i = n; i; i--) ifac[i - 1] = 1ll * ifac[i] * i % mod;
	dfs(1, 0);
	int x = 0, y = 0;
	for (int i = 1; i <= n; i++)
		if (g[i] == mn) (x ? y : x) = i;
	if (y) cout << 1ll * fac[n / 2] * fac[n / 2] % mod;
	else {
		f[0] = 1; int sum = 0, ans = 0;
		for (auto u : E[x]) {
			dfs(u, x); memset(nf, 0, sizeof(nf));
			for (int i = 0; i <= sum; i++)
				for (int j = 0; j <= siz[u]; j++)
					nf[i + j] = (nf[i + j] + 1ll * f[i] * fac[siz[u]] % mod * fac[siz[u]] % mod * ifac[j] % mod * ifac[siz[u] - j] % mod * ifac[siz[u] - j]) % mod;
			swap(f, nf); sum += siz[u];
		}
		for (int i = 0; i < n; i++) ans = (ans + 1ll * f[i] * ((i & 1) ? mod - 1 : 1) % mod * fac[n - i]) % mod;
		cout << ans;
	}
	return 0;
}
```