#include <bits/stdc++.h>

const int mod = 1000000007;
typedef long long LL;
void reduce(int & x) { x += x >> 31 & mod; }
const int MAXN = 5010;
int head[MAXN], nxt[MAXN << 1], to[MAXN << 1], tot;
void addedge(int b, int e) {
	nxt[++tot] = head[b]; to[head[b] = tot] = e;
	nxt[++tot] = head[e]; to[head[e] = tot] = b;
}
int n, rtv, rt, sz[MAXN];
void getroot(int u, int f = 0) {
	int ma = 0; sz[u] = 1;
	for (int i = head[u]; i; i = nxt[i])
		if (to[i] != f) {
			getroot(to[i], u);
			ma = std::max(ma, sz[to[i]]);
			sz[u] += sz[to[i]];
		}
	ma = std::max(ma, n - sz[u]);
	ma < rtv ? (rtv = ma, rt = u) : 0;
}
int fac[MAXN], inv[MAXN];
int li[MAXN], bak;
int dp[MAXN];
int C(int a, int b) {
	return (LL) fac[a] * inv[b] % mod * inv[a - b] % mod;
}
int D(int a, int b) {
	return (LL) fac[a] * inv[a - b] % mod;
}

int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(0);
	std::cin >> n;
	fac[0] = fac[1] = inv[0] = inv[1] = 1;
	for (int i = 2; i <= n; ++i) {
		fac[i] = (LL) fac[i - 1] * i % mod;
		inv[i] = (LL) inv[mod % i] * (mod - mod / i) % mod;
	}
	for (int i = 2; i <= n; ++i) inv[i] = (LL) inv[i] * inv[i - 1] % mod;
	for (int i = 1, t1, t2; i < n; ++i)
		std::cin >> t1 >> t2, addedge(t1, t2);
	rtv = n + 1; getroot(1);
	int ans = 0;
	if (rtv * 2 == n) ans = (LL) fac[n / 2] * fac[n / 2] % mod;
	else {
		for (int i = head[rt]; i; i = nxt[i])
			if (sz[to[i]] <= n / 2) li[++bak] = sz[to[i]];
		if (sz[rt] != n) li[++bak] = n - sz[rt];
		for (int i = *dp = 1, hi = 0; i <= bak; hi += li[i++])
			for (int j = hi + li[i]; ~j; --j) {
				LL t = 0;
				for (int k = std::min(j, hi); j - k <= li[i] && ~k; --k)
					t += (LL) dp[k] * C(li[i], j - k) % mod * D(li[i], j - k) % mod;
				dp[j] = t % mod;
			}
		for (int i = 0; i <= n; ++i) {
			int t = (LL) dp[i] * fac[n - i] % mod;
			if (i & 1) reduce(t = -t);
			reduce(ans += t - mod);
		}
	}
	std::cout << ans << std::endl;
	return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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>

const int mod = 1000000007;
typedef long long LL;
void reduce(int & x) { x += x >> 31 & mod; }
const int MAXN = 5010;
int head[MAXN], nxt[MAXN << 1], to[MAXN << 1], tot;
void addedge(int b, int e) {
	nxt[++tot] = head[b]; to[head[b] = tot] = e;
	nxt[++tot] = head[e]; to[head[e] = tot] = b;
}
int n, rtv, rt, sz[MAXN];
void getroot(int u, int f = 0) {
	int ma = 0; sz[u] = 1;
	for (int i = head[u]; i; i = nxt[i])
		if (to[i] != f) {
			getroot(to[i], u);
			ma = std::max(ma, sz[to[i]]);
			sz[u] += sz[to[i]];
		}
	ma = std::max(ma, n - sz[u]);
	ma < rtv ? (rtv = ma, rt = u) : 0;
}
int fac[MAXN], inv[MAXN];
int li[MAXN], bak;
int dp[MAXN];
int C(int a, int b) {
	return (LL) fac[a] * inv[b] % mod * inv[a - b] % mod;
}
int D(int a, int b) {
	return (LL) fac[a] * inv[a - b] % mod;
}

int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(0);
	std::cin >> n;
	fac[0] = fac[1] = inv[0] = inv[1] = 1;
	for (int i = 2; i <= n; ++i) {
		fac[i] = (LL) fac[i - 1] * i % mod;
		inv[i] = (LL) inv[mod % i] * (mod - mod / i) % mod;
	}
	for (int i = 2; i <= n; ++i) inv[i] = (LL) inv[i] * inv[i - 1] % mod;
	for (int i = 1, t1, t2; i < n; ++i)
		std::cin >> t1 >> t2, addedge(t1, t2);
	rtv = n + 1; getroot(1);
	int ans = 0;
	if (rtv * 2 == n) ans = (LL) fac[n / 2] * fac[n / 2] % mod;
	else {
		for (int i = head[rt]; i; i = nxt[i])
			if (sz[to[i]] <= n / 2) li[++bak] = sz[to[i]];
		if (sz[rt] != n) li[++bak] = n - sz[rt];
		for (int i = *dp = 1, hi = 0; i <= bak; hi += li[i++])
			for (int j = hi + li[i]; ~j; --j) {
				LL t = 0;
				for (int k = std::min(j, hi); j - k <= li[i] && ~k; --k)
					t += (LL) dp[k] * C(li[i], j - k) % mod * D(li[i], j - k) % mod;
				dp[j] = t % mod;
			}
		for (int i = 0; i <= n; ++i) {
			int t = (LL) dp[i] * fac[n - i] % mod;
			if (i & 1) reduce(t = -t);
			reduce(ans += t - mod);
		}
	}
	std::cout << ans << std::endl;
	return 0;
}

```