#include <bits/stdc++.h>

typedef long long ll;
const int N = 5054, M = N * 2, mod = 1000000007;

int n, m = 0, E = 0;
int to[M], first[N], next[M];
int fact[N], finv[N];
int a[N], f[N];
int cG = 0, G[3];

inline void up(int &x, const int y) {x < y ? x = y : 0;}
ll PowerMod(ll a, int n, ll c = 1) {for (; n; n >>= 1, a = a * a % mod) if (n & 1) c = c * a % mod; return c;}

void init(int n) {
	int i;
	for (*fact = i = 1; i <= n; ++i) fact[i] = (ll)fact[i - 1] * i % mod;
	finv[n] = PowerMod(fact[n], mod - 2);
	for (i = n; i; --i) finv[i - 1] = (ll)finv[i] * i % mod;
}

inline ll A(int n, int r) {return (ll)fact[n] * finv[n - r] % mod;}
inline ll C(int n, int r) {return (ll)fact[n] * finv[r] % mod * finv[n - r] % mod;}

inline void addedge(int u, int v) {
	to[++E] = v, next[E] = first[u], first[u] = E;
	to[++E] = u, next[E] = first[v], first[v] = E;
}

int dfs(int x, int px = 0, bool upd = false) {
	int i, y, Sx = 1, Sy, max = 0;
	for (i = first[x]; i; i = next[i])
		if ((y = to[i]) != px)
			Sx += Sy = dfs(y, x, upd), up(max, Sy);
	fprintf(stderr, "%d %d %d\n",x,Sx,max);
	if (up(max, n - Sx), upd && max <= n / 2) G[cG++] = x;
	return Sx;
}

int main() {
	int i, j, k, u, v, s = 0, ans = 0;
	scanf("%d", &n), init(n);
	for (i = 1; i < n; ++i)	scanf("%d%d", &u, &v), addedge(u, v);
	dfs(1, 0, true);
	if (cG == 2) return printf("%d\n", int((ll)fact[n / 2] * fact[n / 2] % mod)), 0;
	assert(cG == 1);
	for (i = first[*G]; i; i = next[i]) a[m++] = dfs(to[i], *G);
	for (*f = 1, i = 0; i < m; s += a[i++])
		for (j = s; j >= 0; --j)
			for (k = 1; k <= a[i]; ++k)
				f[j + k] = (f[j + k] + C(a[i], k) * A(a[i], k) % mod * f[j]) % mod;
	for (i = 0; i <= n; ++i) ans = (ans + ll(i & 1 ? mod - f[i] : f[i]) * fact[n - i]) % mod;
	printf("%d\n", ans);
	return 0;
}
### Prompt

Your task is to create 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>

typedef long long ll;
const int N = 5054, M = N * 2, mod = 1000000007;

int n, m = 0, E = 0;
int to[M], first[N], next[M];
int fact[N], finv[N];
int a[N], f[N];
int cG = 0, G[3];

inline void up(int &x, const int y) {x < y ? x = y : 0;}
ll PowerMod(ll a, int n, ll c = 1) {for (; n; n >>= 1, a = a * a % mod) if (n & 1) c = c * a % mod; return c;}

void init(int n) {
	int i;
	for (*fact = i = 1; i <= n; ++i) fact[i] = (ll)fact[i - 1] * i % mod;
	finv[n] = PowerMod(fact[n], mod - 2);
	for (i = n; i; --i) finv[i - 1] = (ll)finv[i] * i % mod;
}

inline ll A(int n, int r) {return (ll)fact[n] * finv[n - r] % mod;}
inline ll C(int n, int r) {return (ll)fact[n] * finv[r] % mod * finv[n - r] % mod;}

inline void addedge(int u, int v) {
	to[++E] = v, next[E] = first[u], first[u] = E;
	to[++E] = u, next[E] = first[v], first[v] = E;
}

int dfs(int x, int px = 0, bool upd = false) {
	int i, y, Sx = 1, Sy, max = 0;
	for (i = first[x]; i; i = next[i])
		if ((y = to[i]) != px)
			Sx += Sy = dfs(y, x, upd), up(max, Sy);
	fprintf(stderr, "%d %d %d\n",x,Sx,max);
	if (up(max, n - Sx), upd && max <= n / 2) G[cG++] = x;
	return Sx;
}

int main() {
	int i, j, k, u, v, s = 0, ans = 0;
	scanf("%d", &n), init(n);
	for (i = 1; i < n; ++i)	scanf("%d%d", &u, &v), addedge(u, v);
	dfs(1, 0, true);
	if (cG == 2) return printf("%d\n", int((ll)fact[n / 2] * fact[n / 2] % mod)), 0;
	assert(cG == 1);
	for (i = first[*G]; i; i = next[i]) a[m++] = dfs(to[i], *G);
	for (*f = 1, i = 0; i < m; s += a[i++])
		for (j = s; j >= 0; --j)
			for (k = 1; k <= a[i]; ++k)
				f[j + k] = (f[j + k] + C(a[i], k) * A(a[i], k) % mod * f[j]) % mod;
	for (i = 0; i <= n; ++i) ans = (ans + ll(i & 1 ? mod - f[i] : f[i]) * fact[n - i]) % mod;
	printf("%d\n", ans);
	return 0;
}
```