#include <stdio.h>
#include <vector>

using namespace std;

#define MAXN 5005

typedef long long lint;

const lint MOD = 1e9 + 7;
vector<int> ed[MAXN];
int sz[MAXN], par[MAXN];
vector<int> s;
lint fac[MAXN], facinv[MAXN], dp[MAXN][MAXN];

void dfs(int x) {
	sz[x] = 1;
	for(auto a : ed[x]) if(a != par[x]) {
		par[a] = x;
		dfs(a);
		sz[x] += sz[a];
	}
}

lint pow(lint a, int b) {
	lint ans = 1;
	for(int i = 0; (1 << i) <= b; i++, a = a * a % MOD) if(b & (1 << i)) ans = ans * a % MOD;
	return ans;
}

int main() {
	int N;
	int u, v;

	scanf("%d", &N);
	for(int i = 0; i < N - 1; i++) {
		scanf("%d%d", &u, &v);
		ed[u].push_back(v);
		ed[v].push_back(u);
	}

	dfs(1);
	int ct = 1;
	while(true) {
		if(sz[ct] * 2 < N) ct = par[ct];
		else {
			bool b = false;
			for(auto a : ed[ct]) if(a != par[ct] && sz[a] * 2 > N) {
				ct = a;
				b = true;
				break;
			}
			if(!b) break;
		}
	}
	s.push_back(1);
	if(ct != 1) s.push_back(N - sz[ct]);
	for(auto a : ed[ct]) if(a != par[ct]) s.push_back(sz[a]);

	//for(auto a : s) printf("%d ", a);
	//printf("\n");

	fac[0] = 1ll;
	for(int i = 1; i <= N; i++) fac[i] = fac[i - 1] * i % MOD;
	for(int i = 0; i <= N; i++) facinv[i] = pow(fac[i], MOD - 2);

	dp[0][0] = 1ll;
	for(int i = 1; i < s.size(); i++) for(int j = 0; j < N; j++) {
		for(int k = 0; k <= j && k <= s[i]; k++)
			dp[i][j] = (dp[i][j] + dp[i - 1][j - k] * facinv[k] % MOD * pow(facinv[s[i] - k], 2) % MOD) % MOD;
	}

	lint ans = 0ll;
	for(int i = 0; i < N; i++) ans = (ans + pow(-1ll, i) * fac[N - i] * dp[s.size() - 1][i] % MOD + MOD) % MOD;
	for(auto a : s) ans = ans * pow(fac[a], 2) % MOD;
	
	printf("%lld", ans);
	return 0;
}

### Prompt

Generate 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 <stdio.h>
#include <vector>

using namespace std;

#define MAXN 5005

typedef long long lint;

const lint MOD = 1e9 + 7;
vector<int> ed[MAXN];
int sz[MAXN], par[MAXN];
vector<int> s;
lint fac[MAXN], facinv[MAXN], dp[MAXN][MAXN];

void dfs(int x) {
	sz[x] = 1;
	for(auto a : ed[x]) if(a != par[x]) {
		par[a] = x;
		dfs(a);
		sz[x] += sz[a];
	}
}

lint pow(lint a, int b) {
	lint ans = 1;
	for(int i = 0; (1 << i) <= b; i++, a = a * a % MOD) if(b & (1 << i)) ans = ans * a % MOD;
	return ans;
}

int main() {
	int N;
	int u, v;

	scanf("%d", &N);
	for(int i = 0; i < N - 1; i++) {
		scanf("%d%d", &u, &v);
		ed[u].push_back(v);
		ed[v].push_back(u);
	}

	dfs(1);
	int ct = 1;
	while(true) {
		if(sz[ct] * 2 < N) ct = par[ct];
		else {
			bool b = false;
			for(auto a : ed[ct]) if(a != par[ct] && sz[a] * 2 > N) {
				ct = a;
				b = true;
				break;
			}
			if(!b) break;
		}
	}
	s.push_back(1);
	if(ct != 1) s.push_back(N - sz[ct]);
	for(auto a : ed[ct]) if(a != par[ct]) s.push_back(sz[a]);

	//for(auto a : s) printf("%d ", a);
	//printf("\n");

	fac[0] = 1ll;
	for(int i = 1; i <= N; i++) fac[i] = fac[i - 1] * i % MOD;
	for(int i = 0; i <= N; i++) facinv[i] = pow(fac[i], MOD - 2);

	dp[0][0] = 1ll;
	for(int i = 1; i < s.size(); i++) for(int j = 0; j < N; j++) {
		for(int k = 0; k <= j && k <= s[i]; k++)
			dp[i][j] = (dp[i][j] + dp[i - 1][j - k] * facinv[k] % MOD * pow(facinv[s[i] - k], 2) % MOD) % MOD;
	}

	lint ans = 0ll;
	for(int i = 0; i < N; i++) ans = (ans + pow(-1ll, i) * fac[N - i] * dp[s.size() - 1][i] % MOD + MOD) % MOD;
	for(auto a : s) ans = ans * pow(fac[a], 2) % MOD;
	
	printf("%lld", ans);
	return 0;
}

```