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

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

void add(int &x, int y) {
	x += y; if (x >= mod) x -= mod;
}

int mul(int x,int y) {
	return 1LL * x * y % mod;
}

int n;
vector<int> g[N];
int fac[N], C[N][N];
int F[N][N];
int nchild[N];
vector<int> roots;
int a[N], tot = 0;

void dfs(int u,int p) {
	nchild[u] = 1;
	bool flag = true;
	for (int v : g[u]) if (v != p) {
		dfs(v, u);
		nchild[u] += nchild[v];
		if (nchild[v] > (n / 2)) flag = false;
	}
	if (n - nchild[u] > n / 2) flag = false;
	if (flag) roots.push_back(u);
}

int main() {
	scanf("%d", &n);
	fac[0] = 1;
	for (int i = 1; i <= n; ++i) fac[i] = mul(fac[i - 1], i);
	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];
			add(C[i][j], C[i - 1][j - 1]);
		}
	} 
	for (int i = 2; i <= n; ++i) {
		int u, v; scanf("%d %d", &u, &v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1, -1);
	if (roots.size() == 2) return cout << mul(fac[n / 2], fac[n / 2]) << '\n',0;
	else {
		int root = roots[0];
		dfs(root, -1);
		for (int v : g[root]) a[++tot] = nchild[v];
	}
	F[0][0] = 1;
	for (int i = 1; i <= tot; ++i) {
		for (int j = 0; j <= n; ++j) {
			for (int k = 0; k <= a[i]; ++k) {
				if (j >= k) add(F[i][j], mul(mul(F[i - 1][j - k], fac[k]), mul(C[a[i]][k], C[a[i]][k])));
			}
		} 
	}
	int res = 0;
	for (int i = 0; i <= n; ++i) {
		int cur = mul(F[tot][i], fac[n - i]);
		if (i & 1) add(res, mod - cur);
		else add(res, cur);
	}
	cout << res << '\n';
}
### Prompt

Develop a solution in cpp to the problem described below:

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 mod = 1e9 + 7;

void add(int &x, int y) {
	x += y; if (x >= mod) x -= mod;
}

int mul(int x,int y) {
	return 1LL * x * y % mod;
}

int n;
vector<int> g[N];
int fac[N], C[N][N];
int F[N][N];
int nchild[N];
vector<int> roots;
int a[N], tot = 0;

void dfs(int u,int p) {
	nchild[u] = 1;
	bool flag = true;
	for (int v : g[u]) if (v != p) {
		dfs(v, u);
		nchild[u] += nchild[v];
		if (nchild[v] > (n / 2)) flag = false;
	}
	if (n - nchild[u] > n / 2) flag = false;
	if (flag) roots.push_back(u);
}

int main() {
	scanf("%d", &n);
	fac[0] = 1;
	for (int i = 1; i <= n; ++i) fac[i] = mul(fac[i - 1], i);
	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];
			add(C[i][j], C[i - 1][j - 1]);
		}
	} 
	for (int i = 2; i <= n; ++i) {
		int u, v; scanf("%d %d", &u, &v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1, -1);
	if (roots.size() == 2) return cout << mul(fac[n / 2], fac[n / 2]) << '\n',0;
	else {
		int root = roots[0];
		dfs(root, -1);
		for (int v : g[root]) a[++tot] = nchild[v];
	}
	F[0][0] = 1;
	for (int i = 1; i <= tot; ++i) {
		for (int j = 0; j <= n; ++j) {
			for (int k = 0; k <= a[i]; ++k) {
				if (j >= k) add(F[i][j], mul(mul(F[i - 1][j - k], fac[k]), mul(C[a[i]][k], C[a[i]][k])));
			}
		} 
	}
	int res = 0;
	for (int i = 0; i <= n; ++i) {
		int cur = mul(F[tot][i], fac[n - i]);
		if (i & 1) add(res, mod - cur);
		else add(res, cur);
	}
	cout << res << '\n';
}
```