#include <bits/stdc++.h>

#define LL long long
#define pii pair<int,int>
using namespace std;
const int inf = 2147483647;
const int mod = 1e9 + 7;
const int N = 5001;

int _max(int x, int y) {return x > y ? x : y;}
int _min(int x, int y) {return x < y ? x : y;}
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x * f;
}
void put(int x) {
	if(x < 0) putchar('-'), x = -x;
	if(x >= 10) put(x / 10);
	putchar(x % 10 + '0');
}

struct edge {
	int x, y, next;
} e[2 * N]; int len, last[N];
int n, mn, tot[N], f[N], jc[N], inv[N], tmp[N], hh[N], F[N];

int add(int x, int y) {
	x += y;
	return x >= mod ? x - mod : x;
}
int dec(int x, int y) {
	x -= y;
	return x < 0 ? x + mod : x;
}
int pow_mod(int a, int k) {
	int ans = 1;
	while(k) {
		if(k & 1) ans = (LL)ans * a % mod;
		a = (LL)a * a % mod, k /= 2;
	} return ans;
}
int C(int n, int m) {return (LL)jc[n] * inv[m] % mod * inv[n - m] % mod;}

void ins(int x, int y) {
	e[++len].x = x, e[len].y = y;
	e[len].next = last[x]; last[x], last[x] = len;
}

void findrt(int x, int fa) {
	tot[x] = 1;
	for(int k = last[x]; k; k = e[k].next) {
		int y = e[k].y;
		if(y != fa) {
			findrt(y, x);
			tot[x] += tot[y];
			f[x] = _max(f[x], tot[y]);
		}
	} f[x] = _max(f[x], n - tot[x]);
	mn = _min(mn, f[x]);
}

int main() {
	n = read();
	for(int i = 1; i < n; i++) {
		int x = read(), y = read();
		ins(x, y), ins(y, x);
	} mn = n + 1, findrt(1, 0);
	int h1 = 0, h2 = 0;
	for(int i = 1; i <= n; i++) {
		if(f[i] == mn) h2 = h1, h1 = i;
	} if(h2) {
		int ans = 1;
		for(int i = 1; i <= n / 2; i++) ans = (LL)ans * i % mod;
		put((LL)ans * ans % mod), puts("");
	} else {
		jc[0] = 1; for(int i = 1; i <= n; i++) jc[i] = (LL)jc[i - 1] * i % mod;
		inv[n] = pow_mod(jc[n], mod - 2); for(int i = n; i >= 1; i--) inv[i - 1] = (LL)inv[i] * i % mod;
		F[0] = 1; int s = 0;
		for(int k = last[h1]; k; k = e[k].next) {
			int y = e[k].y;
			findrt(y, h1);
			for(int i = 0; i <= s + tot[y]; i++) tmp[i] = 0;
			for(int j = 0; j <= tot[y]; j++) {
				for(int i = s; i >= 0; i--) {
					tmp[i + j] = add(tmp[i + j], (LL)F[i] * jc[tot[y]] % mod * inv[tot[y] - j] % mod * C(tot[y], j) % mod);
				}
			} s += tot[y];
			for(int i = 0; i <= s; i++) F[i] = tmp[i];
		} int ans = 0;
		for(int i = 0; i < n; i++) ans = i & 1 ? dec(ans, (LL)F[i] * jc[n - i] % mod) : add(ans, (LL)F[i] * jc[n - i] % mod);
		put(ans), puts("");
	}
	return 0;
}

### Prompt

Please formulate 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>

#define LL long long
#define pii pair<int,int>
using namespace std;
const int inf = 2147483647;
const int mod = 1e9 + 7;
const int N = 5001;

int _max(int x, int y) {return x > y ? x : y;}
int _min(int x, int y) {return x < y ? x : y;}
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x * f;
}
void put(int x) {
	if(x < 0) putchar('-'), x = -x;
	if(x >= 10) put(x / 10);
	putchar(x % 10 + '0');
}

struct edge {
	int x, y, next;
} e[2 * N]; int len, last[N];
int n, mn, tot[N], f[N], jc[N], inv[N], tmp[N], hh[N], F[N];

int add(int x, int y) {
	x += y;
	return x >= mod ? x - mod : x;
}
int dec(int x, int y) {
	x -= y;
	return x < 0 ? x + mod : x;
}
int pow_mod(int a, int k) {
	int ans = 1;
	while(k) {
		if(k & 1) ans = (LL)ans * a % mod;
		a = (LL)a * a % mod, k /= 2;
	} return ans;
}
int C(int n, int m) {return (LL)jc[n] * inv[m] % mod * inv[n - m] % mod;}

void ins(int x, int y) {
	e[++len].x = x, e[len].y = y;
	e[len].next = last[x]; last[x], last[x] = len;
}

void findrt(int x, int fa) {
	tot[x] = 1;
	for(int k = last[x]; k; k = e[k].next) {
		int y = e[k].y;
		if(y != fa) {
			findrt(y, x);
			tot[x] += tot[y];
			f[x] = _max(f[x], tot[y]);
		}
	} f[x] = _max(f[x], n - tot[x]);
	mn = _min(mn, f[x]);
}

int main() {
	n = read();
	for(int i = 1; i < n; i++) {
		int x = read(), y = read();
		ins(x, y), ins(y, x);
	} mn = n + 1, findrt(1, 0);
	int h1 = 0, h2 = 0;
	for(int i = 1; i <= n; i++) {
		if(f[i] == mn) h2 = h1, h1 = i;
	} if(h2) {
		int ans = 1;
		for(int i = 1; i <= n / 2; i++) ans = (LL)ans * i % mod;
		put((LL)ans * ans % mod), puts("");
	} else {
		jc[0] = 1; for(int i = 1; i <= n; i++) jc[i] = (LL)jc[i - 1] * i % mod;
		inv[n] = pow_mod(jc[n], mod - 2); for(int i = n; i >= 1; i--) inv[i - 1] = (LL)inv[i] * i % mod;
		F[0] = 1; int s = 0;
		for(int k = last[h1]; k; k = e[k].next) {
			int y = e[k].y;
			findrt(y, h1);
			for(int i = 0; i <= s + tot[y]; i++) tmp[i] = 0;
			for(int j = 0; j <= tot[y]; j++) {
				for(int i = s; i >= 0; i--) {
					tmp[i + j] = add(tmp[i + j], (LL)F[i] * jc[tot[y]] % mod * inv[tot[y] - j] % mod * C(tot[y], j) % mod);
				}
			} s += tot[y];
			for(int i = 0; i <= s; i++) F[i] = tmp[i];
		} int ans = 0;
		for(int i = 0; i < n; i++) ans = i & 1 ? dec(ans, (LL)F[i] * jc[n - i] % mod) : add(ans, (LL)F[i] * jc[n - i] % mod);
		put(ans), puts("");
	}
	return 0;
}

```