#include <bits/stdc++.h>

typedef long long LL;
const int N = 5005, mod = 1000000007;

int inv[N];
void init(int n) {
	inv[1] = 1;
	for (int i = 2; i <= n; ++i)
		inv[i] = (LL) inv[mod % i] * (mod - mod / i) % mod;
}

int n, head[N], tot, G;
struct edge { int to, nxt; } e[N << 1];
void link(int x, int y) {
	e[++tot] = (edge) {y, head[x]}, head[x] = tot;
	e[++tot] = (edge) {x, head[y]}, head[y] = tot;
}

int dfs(int x, int f = 0) {
	int max = 0, size = 1;
	for (int i = head[x]; i; i = e[i].nxt) if (e[i].to != f) {
		int ret = dfs(e[i].to, x); max = std::max(max, ret), size += ret;
		if (ret << 1 == n) {
			int ans = 1;
			for (int i = 1; i <= ret; ++i) ans = (LL) ans * i % mod;
			std::cout << (LL) ans * ans % mod << '\n', std::exit(0);
		}
	}
	max = std::max(max, n - size);
	if (max << 1 < n) G = x;
	return size;
}

int f[N], g[N], h[N], deg;
int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0);
	std::cin >> n, init(n);
	for (int i = 1, x, y; i < n; ++i)
		std::cin >> x >> y, link(x, y);
	dfs(1), deg = 0, f[0] = 1;
	for (int i = head[G]; i; i = e[i].nxt) {
		int k = dfs(e[i].to, G); g[0] = 1;
		for (int j = 0; j < k; ++j)
			g[j + 1] = (LL) g[j] * (j - k + mod) % mod * (k - j) % mod * inv[j + 1] % mod;
		for (int j = 0; j <= deg + k; ++j) h[j] = 0;
		for (int j = 0; j <= deg; ++j)
			for (int l = 0; l <= k; ++l) h[j + l] = (h[j + l] + (LL) f[j] * g[l]) % mod;
		for (int j = 0; j <= deg + k; ++j) f[j] = h[j]; deg += k;
	}
	int ans = 0;
	for (int i = 0; i <= n; ++i)
		ans = (ans * (n - i + 1LL) + f[i]) % mod;
	std::cout << ans << '\n';
	return 0;
}
### Prompt

Create a solution in CPP for 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 = 5005, mod = 1000000007;

int inv[N];
void init(int n) {
	inv[1] = 1;
	for (int i = 2; i <= n; ++i)
		inv[i] = (LL) inv[mod % i] * (mod - mod / i) % mod;
}

int n, head[N], tot, G;
struct edge { int to, nxt; } e[N << 1];
void link(int x, int y) {
	e[++tot] = (edge) {y, head[x]}, head[x] = tot;
	e[++tot] = (edge) {x, head[y]}, head[y] = tot;
}

int dfs(int x, int f = 0) {
	int max = 0, size = 1;
	for (int i = head[x]; i; i = e[i].nxt) if (e[i].to != f) {
		int ret = dfs(e[i].to, x); max = std::max(max, ret), size += ret;
		if (ret << 1 == n) {
			int ans = 1;
			for (int i = 1; i <= ret; ++i) ans = (LL) ans * i % mod;
			std::cout << (LL) ans * ans % mod << '\n', std::exit(0);
		}
	}
	max = std::max(max, n - size);
	if (max << 1 < n) G = x;
	return size;
}

int f[N], g[N], h[N], deg;
int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0);
	std::cin >> n, init(n);
	for (int i = 1, x, y; i < n; ++i)
		std::cin >> x >> y, link(x, y);
	dfs(1), deg = 0, f[0] = 1;
	for (int i = head[G]; i; i = e[i].nxt) {
		int k = dfs(e[i].to, G); g[0] = 1;
		for (int j = 0; j < k; ++j)
			g[j + 1] = (LL) g[j] * (j - k + mod) % mod * (k - j) % mod * inv[j + 1] % mod;
		for (int j = 0; j <= deg + k; ++j) h[j] = 0;
		for (int j = 0; j <= deg; ++j)
			for (int l = 0; l <= k; ++l) h[j + l] = (h[j + l] + (LL) f[j] * g[l]) % mod;
		for (int j = 0; j <= deg + k; ++j) f[j] = h[j]; deg += k;
	}
	int ans = 0;
	for (int i = 0; i <= n; ++i)
		ans = (ans * (n - i + 1LL) + f[i]) % mod;
	std::cout << ans << '\n';
	return 0;
}
```