#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define drep(i, a, b) for(int i = (a), i##_end_ = (b); i >= i##_end_; --i)
#define clar(a, b) memset((a), (b), sizeof(a))
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef long long LL;
typedef long double LD;
int read() {
	char ch = getchar();
	int x = 0, flag = 1;
	for (;!isdigit(ch); ch = getchar()) if (ch == '-') flag *= -1;
	for (;isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
	return x * flag;
}
void write(int x) {
	if (x < 0) putchar('-'), x = -x;
	if (x >= 10) write(x / 10);
	putchar(x % 10 + 48);
}

const int Maxn = 5009, Mod = 1e9 + 7;
struct edge {
	int to, nxt;
}g[Maxn << 1];
int n, head[Maxn], e;
int fac[Maxn], invFac[Maxn];

LL fpm(LL base, LL tims) {
	LL r = 1;
	while (tims) {
		if (tims & 1) r = 1ll * r * base % Mod;
		base = 1ll * base * base % Mod;
		tims >>= 1;
	}
	return r;
}

void add(int u, int v) {
	g[++e] = (edge){v, head[u]}, head[u] = e;
}

void init() {
	clar(head, -1); e = 0;
	n = read();
	rep (i, 2, n) {
		int u = read(), v = read();
		add(u, v), add(v, u);
	}

	fac[0] = 1;
	rep (i, 1, n + 2) fac[i] = fac[i - 1] * 1ll * i % Mod;
	invFac[n + 2] = fpm(fac[n + 2], Mod - 2);
	drep (i, n + 1, 0) invFac[i] = invFac[i + 1] * (i + 1ll) % Mod;
}

int size[Maxn];
void dfsPre(int u, int pa) {
	size[u] = 1;
	for (int i = head[u]; ~i; i = g[i].nxt) {
		int v = g[i].to;
		if (v != pa) {
			dfsPre(v, u);
			size[u] += size[v];
		}
	}
}

int cen, branch, flag;
void dfsRt(int u, int pa) {
	int	bbs = size[1] - size[u];
	for (int i = head[u]; ~i; i = g[i].nxt) {
		int v = g[i].to;
		if (v != pa) {
			dfsRt(v, u);
			bbs = max(bbs, size[v]);
		}
	}
	if (bbs < branch) branch = bbs, cen = u, flag = 0;
	else if (bbs == branch) flag = 1; 
}

LL C(int n, int m) {
	return (n < m) ? 0 : (fac[n] * 1ll * invFac[m] % Mod * invFac[n - m] % Mod);
}

LL dp[2][Maxn], s[Maxn];

void solve() {
	dfsPre(1, 0); branch = INT_MAX; dfsRt(1, 0);
	if (flag) {
		cout << fac[n / 2] * 1ll * fac[n / 2] % Mod << endl;
		return ;
	}
	rep (i, 1, n) size[i] = 0;
	dfsPre(cen, 0);
	int deg = 0, sum = 0;
	for (int i = head[cen]; ~i; i = g[i].nxt) s[++deg] = size[g[i].to];
	sort(s + 1, s + deg + 1);
	dp[0][0] = 1;
	rep (i, 1, deg) {
		clar(dp[i & 1], 0);
		drep (j, (sum += s[i]), 0) {
			LL &res = dp[i & 1][j]; res += dp[(i & 1) ^ 1][j];
			rep (k, 1, min(1ll * j, s[i])) 
				(res += dp[(i & 1) ^ 1][j - k] * 1ll * C(s[i], k) % Mod * C(s[i], k) % Mod * fac[k] % Mod) %= Mod;
		}
	}
	LL ans = fac[n];
	rep (i, 1, n - 1) {
		LL res = ((dp[deg & 1][i] * ((i & 1) ? -1ll : 1ll) * fac[n - i] % Mod) + Mod) % Mod;
		(ans += res) %= Mod;
	}
	cout << ans << endl;
}

int main() {
//	freopen("bosky.in", "r", stdin);
//	freopen("bosky.out", "w", stdout);

	init();
	solve();

#ifdef Qrsikno
	debug("\nRunning time: %.3lf(s)\n", clock() * 1.0 / CLOCKS_PER_SEC);
#endif
	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<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define drep(i, a, b) for(int i = (a), i##_end_ = (b); i >= i##_end_; --i)
#define clar(a, b) memset((a), (b), sizeof(a))
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef long long LL;
typedef long double LD;
int read() {
	char ch = getchar();
	int x = 0, flag = 1;
	for (;!isdigit(ch); ch = getchar()) if (ch == '-') flag *= -1;
	for (;isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
	return x * flag;
}
void write(int x) {
	if (x < 0) putchar('-'), x = -x;
	if (x >= 10) write(x / 10);
	putchar(x % 10 + 48);
}

const int Maxn = 5009, Mod = 1e9 + 7;
struct edge {
	int to, nxt;
}g[Maxn << 1];
int n, head[Maxn], e;
int fac[Maxn], invFac[Maxn];

LL fpm(LL base, LL tims) {
	LL r = 1;
	while (tims) {
		if (tims & 1) r = 1ll * r * base % Mod;
		base = 1ll * base * base % Mod;
		tims >>= 1;
	}
	return r;
}

void add(int u, int v) {
	g[++e] = (edge){v, head[u]}, head[u] = e;
}

void init() {
	clar(head, -1); e = 0;
	n = read();
	rep (i, 2, n) {
		int u = read(), v = read();
		add(u, v), add(v, u);
	}

	fac[0] = 1;
	rep (i, 1, n + 2) fac[i] = fac[i - 1] * 1ll * i % Mod;
	invFac[n + 2] = fpm(fac[n + 2], Mod - 2);
	drep (i, n + 1, 0) invFac[i] = invFac[i + 1] * (i + 1ll) % Mod;
}

int size[Maxn];
void dfsPre(int u, int pa) {
	size[u] = 1;
	for (int i = head[u]; ~i; i = g[i].nxt) {
		int v = g[i].to;
		if (v != pa) {
			dfsPre(v, u);
			size[u] += size[v];
		}
	}
}

int cen, branch, flag;
void dfsRt(int u, int pa) {
	int	bbs = size[1] - size[u];
	for (int i = head[u]; ~i; i = g[i].nxt) {
		int v = g[i].to;
		if (v != pa) {
			dfsRt(v, u);
			bbs = max(bbs, size[v]);
		}
	}
	if (bbs < branch) branch = bbs, cen = u, flag = 0;
	else if (bbs == branch) flag = 1; 
}

LL C(int n, int m) {
	return (n < m) ? 0 : (fac[n] * 1ll * invFac[m] % Mod * invFac[n - m] % Mod);
}

LL dp[2][Maxn], s[Maxn];

void solve() {
	dfsPre(1, 0); branch = INT_MAX; dfsRt(1, 0);
	if (flag) {
		cout << fac[n / 2] * 1ll * fac[n / 2] % Mod << endl;
		return ;
	}
	rep (i, 1, n) size[i] = 0;
	dfsPre(cen, 0);
	int deg = 0, sum = 0;
	for (int i = head[cen]; ~i; i = g[i].nxt) s[++deg] = size[g[i].to];
	sort(s + 1, s + deg + 1);
	dp[0][0] = 1;
	rep (i, 1, deg) {
		clar(dp[i & 1], 0);
		drep (j, (sum += s[i]), 0) {
			LL &res = dp[i & 1][j]; res += dp[(i & 1) ^ 1][j];
			rep (k, 1, min(1ll * j, s[i])) 
				(res += dp[(i & 1) ^ 1][j - k] * 1ll * C(s[i], k) % Mod * C(s[i], k) % Mod * fac[k] % Mod) %= Mod;
		}
	}
	LL ans = fac[n];
	rep (i, 1, n - 1) {
		LL res = ((dp[deg & 1][i] * ((i & 1) ? -1ll : 1ll) * fac[n - i] % Mod) + Mod) % Mod;
		(ans += res) %= Mod;
	}
	cout << ans << endl;
}

int main() {
//	freopen("bosky.in", "r", stdin);
//	freopen("bosky.out", "w", stdout);

	init();
	solve();

#ifdef Qrsikno
	debug("\nRunning time: %.3lf(s)\n", clock() * 1.0 / CLOCKS_PER_SEC);
#endif
	return 0;
}


```