#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int V = 5010;
const int P = 1000000007;
char get() {
	static char buf[V], *p1 = buf, *p2 = buf;
	if (p1 == p2) {
		p2 = (p1 = buf) + fread(buf, 1, V, stdin);
		if (p1 == p2) return EOF;
	}
	return *p1++;
}
void Read(int &x) {
	x = 0; static char c;
	while (c > '9' || c < '0') c = get();
	while (c >= '0' && c <= '9') {
		x = x * 10 + c - '0'; c = get();
	}
}
void Add(int &x, int y) {
	(x += y) %= P;
}
int N, fac[V], c[V][V], f[V], w[2];
vector<int> G[V];
void Init(int n) {
	int i, j;
	w[0] = 1; w[1] = -1;
	fac[0] = 1; for (i = 1; i <= n; i++) Add(fac[i], 1LL * fac[i - 1] * i % P);
	c[0][0] = 1;
	for (i = 1; i <= n; i++) {
		c[i][0] = 1;
		for (j = 1; j <= i; j++) Add(c[i][j], c[i - 1][j] + c[i - 1][j - 1]);
	}
}
int siz[V], mxs[V];
void Dfs(int u, int fa) {
	siz[u] = 1;
	for (auto v : G[u]) {
		if (v == fa) continue;
		Dfs(v, u); siz[u] += siz[v];
		mxs[u] = max(mxs[u], siz[v]);
	}
	mxs[u] = max(mxs[u], N - siz[u]);
}
int main() {
	int i, j, u, v;
	Read(N); Init(N);
	for (i = 1; i < N; i++) {
		Read(u); Read(v);
		G[u].emplace_back(v); G[v].emplace_back(u);
	}
	Dfs(1, 0); int Rt = 0;
	for (i = 1; i <= N; i++)
		if (mxs[i] <= N / 2) {
			if (Rt) {
				printf("%lld\n", 1LL * fac[N / 2] * fac[N / 2] % P);
				return 0;
			}
			else Rt = i;
		}
	Dfs(Rt, 0); f[0] = 1;
	for (auto v : G[Rt]) {
		int Now = siz[v];
		for (i = N; i; i--)
			for (j = i - 1; ~j && i - j <= Now; j--)
				Add(f[i], 1LL * f[j] * c[Now][i - j] % P * c[Now][i - j] % P * fac[i - j] % P);
	}
	int Ans = 0;
	for (i = 0; i <= N; i++) {
		Add(Ans, (P + 1LL * w[i % 2] * f[i] % P * fac[N - i] % P) % P);
	}
	printf("%d\n", Ans);
	return 0;
}
### Prompt

Develop a solution in cpp 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 <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int V = 5010;
const int P = 1000000007;
char get() {
	static char buf[V], *p1 = buf, *p2 = buf;
	if (p1 == p2) {
		p2 = (p1 = buf) + fread(buf, 1, V, stdin);
		if (p1 == p2) return EOF;
	}
	return *p1++;
}
void Read(int &x) {
	x = 0; static char c;
	while (c > '9' || c < '0') c = get();
	while (c >= '0' && c <= '9') {
		x = x * 10 + c - '0'; c = get();
	}
}
void Add(int &x, int y) {
	(x += y) %= P;
}
int N, fac[V], c[V][V], f[V], w[2];
vector<int> G[V];
void Init(int n) {
	int i, j;
	w[0] = 1; w[1] = -1;
	fac[0] = 1; for (i = 1; i <= n; i++) Add(fac[i], 1LL * fac[i - 1] * i % P);
	c[0][0] = 1;
	for (i = 1; i <= n; i++) {
		c[i][0] = 1;
		for (j = 1; j <= i; j++) Add(c[i][j], c[i - 1][j] + c[i - 1][j - 1]);
	}
}
int siz[V], mxs[V];
void Dfs(int u, int fa) {
	siz[u] = 1;
	for (auto v : G[u]) {
		if (v == fa) continue;
		Dfs(v, u); siz[u] += siz[v];
		mxs[u] = max(mxs[u], siz[v]);
	}
	mxs[u] = max(mxs[u], N - siz[u]);
}
int main() {
	int i, j, u, v;
	Read(N); Init(N);
	for (i = 1; i < N; i++) {
		Read(u); Read(v);
		G[u].emplace_back(v); G[v].emplace_back(u);
	}
	Dfs(1, 0); int Rt = 0;
	for (i = 1; i <= N; i++)
		if (mxs[i] <= N / 2) {
			if (Rt) {
				printf("%lld\n", 1LL * fac[N / 2] * fac[N / 2] % P);
				return 0;
			}
			else Rt = i;
		}
	Dfs(Rt, 0); f[0] = 1;
	for (auto v : G[Rt]) {
		int Now = siz[v];
		for (i = N; i; i--)
			for (j = i - 1; ~j && i - j <= Now; j--)
				Add(f[i], 1LL * f[j] * c[Now][i - j] % P * c[Now][i - j] % P * fac[i - j] % P);
	}
	int Ans = 0;
	for (i = 0; i <= N; i++) {
		Add(Ans, (P + 1LL * w[i % 2] * f[i] % P * fac[N - i] % P) % P);
	}
	printf("%d\n", Ans);
	return 0;
}
```