#include <bits/stdc++.h>
using namespace std;

const int N = 5005;
const int md = 1e9 + 7;

int n;
vector<int> G[N];
int nchild[N];
int fact[N], C[N][N];
int dp[N], tmp[N];
int ans;

void prepare() {
	fact[0] = 1; for (int i = 1; i < N; ++i) fact[i] = 1LL * fact[i-1] * i % md;
	for (int i = 0; i < N; ++i) C[i][0] = 1;
	for (int i = 1; i < N; ++i) {
		for (int j = 1; j <= i; ++j) C[i][j] = (C[i-1][j-1] + C[i-1][j]) % md;
	}
}

void dfs(int u, int p) {
	nchild[u] = 1;
	for (int v : G[u]) if (v != p) {
		dfs(v, u);
		nchild[u] += nchild[v];
	}
}

int find_centroid(int u, int p) {
	for (int v : G[u]) if (v != p && nchild[v] * 2 >= n) {
		return find_centroid(v, u);
	}
	return u;
}

void add(int &x, int y) {
	x += y; while(x >= md) x -= md; if (x < 0) x += md;
}

int solve(vector<int> &a) {
	int sz = a.size();
	memset(dp, 0, sizeof dp);
	dp[0] = 1;

	int sum = 0;
	for (int i = 0; i < sz; ++i) {
		for (int j = 0; j <= sum + a[i]; ++j) tmp[j] = 0;
		for (int j = 0; j <= sum; ++j) for (int k = 0; k <= a[i]; ++k) {
			int mul = 1LL * C[a[i]][k] * C[a[i]][k] % md;
			add(tmp[j + k], 1LL * dp[j] * (1LL * mul * fact[k] % md) % md);
		}
		sum += a[i];
		for (int j = 0; j <= sum; ++j) dp[j] = tmp[j];
	}

	int ret = 0;
	for (int i = 0; i <= sum; ++i) {
		int cur = 1LL * dp[i] * fact[sum - i] % md;
		if (i & 1) add(ret, -cur);
		else add(ret, cur);
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for (int i = 1; i < n; ++i) {
		int u, v; cin >> u >> v;
		G[u].push_back(v); G[v].push_back(u);
	}
	prepare();
	dfs(1, -1);
	int centroid = find_centroid(1, -1);

	if (nchild[centroid] * 2 == n) { 
		// there are two centroids which are connected by an edge
		printf("%d\n", 1LL * fact[n / 2] * fact[n / 2] % md);
		return 0;
	}

	vector<int> vec;
	dfs(centroid, -1);
	for (int v : G[centroid]) {
		vec.push_back(nchild[v]);
	}
	ans += solve(vec);
	vec.push_back(1); // including centroid
	ans += solve(vec);

	printf("%d\n", ans % md);
}
### Prompt

Please create a solution in cpp 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>
using namespace std;

const int N = 5005;
const int md = 1e9 + 7;

int n;
vector<int> G[N];
int nchild[N];
int fact[N], C[N][N];
int dp[N], tmp[N];
int ans;

void prepare() {
	fact[0] = 1; for (int i = 1; i < N; ++i) fact[i] = 1LL * fact[i-1] * i % md;
	for (int i = 0; i < N; ++i) C[i][0] = 1;
	for (int i = 1; i < N; ++i) {
		for (int j = 1; j <= i; ++j) C[i][j] = (C[i-1][j-1] + C[i-1][j]) % md;
	}
}

void dfs(int u, int p) {
	nchild[u] = 1;
	for (int v : G[u]) if (v != p) {
		dfs(v, u);
		nchild[u] += nchild[v];
	}
}

int find_centroid(int u, int p) {
	for (int v : G[u]) if (v != p && nchild[v] * 2 >= n) {
		return find_centroid(v, u);
	}
	return u;
}

void add(int &x, int y) {
	x += y; while(x >= md) x -= md; if (x < 0) x += md;
}

int solve(vector<int> &a) {
	int sz = a.size();
	memset(dp, 0, sizeof dp);
	dp[0] = 1;

	int sum = 0;
	for (int i = 0; i < sz; ++i) {
		for (int j = 0; j <= sum + a[i]; ++j) tmp[j] = 0;
		for (int j = 0; j <= sum; ++j) for (int k = 0; k <= a[i]; ++k) {
			int mul = 1LL * C[a[i]][k] * C[a[i]][k] % md;
			add(tmp[j + k], 1LL * dp[j] * (1LL * mul * fact[k] % md) % md);
		}
		sum += a[i];
		for (int j = 0; j <= sum; ++j) dp[j] = tmp[j];
	}

	int ret = 0;
	for (int i = 0; i <= sum; ++i) {
		int cur = 1LL * dp[i] * fact[sum - i] % md;
		if (i & 1) add(ret, -cur);
		else add(ret, cur);
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for (int i = 1; i < n; ++i) {
		int u, v; cin >> u >> v;
		G[u].push_back(v); G[v].push_back(u);
	}
	prepare();
	dfs(1, -1);
	int centroid = find_centroid(1, -1);

	if (nchild[centroid] * 2 == n) { 
		// there are two centroids which are connected by an edge
		printf("%d\n", 1LL * fact[n / 2] * fact[n / 2] % md);
		return 0;
	}

	vector<int> vec;
	dfs(centroid, -1);
	for (int v : G[centroid]) {
		vec.push_back(nchild[v]);
	}
	ans += solve(vec);
	vec.push_back(1); // including centroid
	ans += solve(vec);

	printf("%d\n", ans % md);
}
```