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

typedef long long ll;
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define db double

const int mod = (int)1e9 + 7;

int mult(int a, int b){
	return a * (ll)b % mod;
}

int bp(int a, int k){
	if (k < 0) k += mod - 1;
	if (k == 0) return 1;
	if (k % 2 == 1){
		return mult(a, bp(a, k - 1));
	} else {
		int q = bp(a, k / 2);
		return mult(q, q);
	}
}

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

int sum(int a, int b){
	int ans = a + b;
	if (ans >= mod) ans -= mod;
	return ans;
}

int sub(int a, int b){
	int ans = a - b;
	if (ans < 0) ans += mod;
	return ans;
}

int n;
vector<int> g[5005];
int fac[5005], invfac[5005];
int sz[5005];

void calcSz(int v, int pred){
	sz[v] = 1;
	for (int to : g[v]) if (to != pred){
		calcSz(to, v);
		sz[v] += sz[to];
	}
}

vector<int> t;
int findCentroid(int v, int pred){
	for (int to : g[v]) if (to != pred){
		if (sz[to] >= (n + 1) / 2) return findCentroid(to, v);
	}
	int sum = n - 1;
	for (int to : g[v]) if (to != pred){
		t.pb(sz[to]);
		sum -= sz[to];
	}
	if (sum != 0) t.pb(sum);
	return v;
}

int dp[5005][5005];

int cnk(int k, int n){
	return mult(fac[n], mult(invfac[k], invfac[n - k]));
}

int main(){
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; i++){
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].pb(b);
		g[b].pb(a);
	}
	fac[0] = 1;
	for (int i = 1; i < 5005; i++) fac[i] = mult(i, fac[i - 1]);
	for (int i = 0; i < 5005; i++) invfac[i] = bp(fac[i], -1);

	calcSz(0, -1);
	int cc = findCentroid(0, -1);
	if (n % 2 == 0 && sz[cc] == n / 2) cout << mult(fac[n / 2], fac[n / 2]), exit(0);

	int ans = 0;
	t.pb(1);

	dp[0][0] = 1;
	for (int i = 0; i < t.size(); i++){
		for (int j = 0; j < 5005; j++) if (dp[i][j]){
			for (int s = 0; s <= t[i]; s++){
				add(dp[i + 1][j + s], mult(dp[i][j], mult(cnk(s, t[i]), mult(fac[s], cnk(s, t[i])))));
			}
		}
	}

	for (int i = 0; i < 5005; i++){
		dp[t.size()][i] = mult(dp[t.size()][i], fac[n - i]);
		if (i % 2 == 0) ans = sum(ans, dp[t.size()][i]);
		else ans = sub(ans, dp[t.size()][i]);
	}

	for (int i = 0; i < 5005; i++) for (int j = 0; j < 5005; j++) dp[i][j] = 0;

	t.pop_back();

	dp[0][0] = 1;
	for (int i = 0; i < t.size(); i++){
		for (int j = 0; j < 5005; j++) if (dp[i][j]){
			for (int s = 0; s <= t[i]; s++){
				add(dp[i + 1][j + s], mult(dp[i][j], mult(cnk(s, t[i]), mult(fac[s], cnk(s, t[i])))));
			}
		}
	}

	for (int i = 0; i < 5005; i++){
		dp[t.size()][i] = mult(dp[t.size()][i], fac[n - i - 1]);
		if (i % 2 == 0) ans = sum(ans, dp[t.size()][i]);
		else ans = sub(ans, dp[t.size()][i]);
	}

	cout << ans;
}       
### 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;

typedef long long ll;
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define db double

const int mod = (int)1e9 + 7;

int mult(int a, int b){
	return a * (ll)b % mod;
}

int bp(int a, int k){
	if (k < 0) k += mod - 1;
	if (k == 0) return 1;
	if (k % 2 == 1){
		return mult(a, bp(a, k - 1));
	} else {
		int q = bp(a, k / 2);
		return mult(q, q);
	}
}

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

int sum(int a, int b){
	int ans = a + b;
	if (ans >= mod) ans -= mod;
	return ans;
}

int sub(int a, int b){
	int ans = a - b;
	if (ans < 0) ans += mod;
	return ans;
}

int n;
vector<int> g[5005];
int fac[5005], invfac[5005];
int sz[5005];

void calcSz(int v, int pred){
	sz[v] = 1;
	for (int to : g[v]) if (to != pred){
		calcSz(to, v);
		sz[v] += sz[to];
	}
}

vector<int> t;
int findCentroid(int v, int pred){
	for (int to : g[v]) if (to != pred){
		if (sz[to] >= (n + 1) / 2) return findCentroid(to, v);
	}
	int sum = n - 1;
	for (int to : g[v]) if (to != pred){
		t.pb(sz[to]);
		sum -= sz[to];
	}
	if (sum != 0) t.pb(sum);
	return v;
}

int dp[5005][5005];

int cnk(int k, int n){
	return mult(fac[n], mult(invfac[k], invfac[n - k]));
}

int main(){
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; i++){
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].pb(b);
		g[b].pb(a);
	}
	fac[0] = 1;
	for (int i = 1; i < 5005; i++) fac[i] = mult(i, fac[i - 1]);
	for (int i = 0; i < 5005; i++) invfac[i] = bp(fac[i], -1);

	calcSz(0, -1);
	int cc = findCentroid(0, -1);
	if (n % 2 == 0 && sz[cc] == n / 2) cout << mult(fac[n / 2], fac[n / 2]), exit(0);

	int ans = 0;
	t.pb(1);

	dp[0][0] = 1;
	for (int i = 0; i < t.size(); i++){
		for (int j = 0; j < 5005; j++) if (dp[i][j]){
			for (int s = 0; s <= t[i]; s++){
				add(dp[i + 1][j + s], mult(dp[i][j], mult(cnk(s, t[i]), mult(fac[s], cnk(s, t[i])))));
			}
		}
	}

	for (int i = 0; i < 5005; i++){
		dp[t.size()][i] = mult(dp[t.size()][i], fac[n - i]);
		if (i % 2 == 0) ans = sum(ans, dp[t.size()][i]);
		else ans = sub(ans, dp[t.size()][i]);
	}

	for (int i = 0; i < 5005; i++) for (int j = 0; j < 5005; j++) dp[i][j] = 0;

	t.pop_back();

	dp[0][0] = 1;
	for (int i = 0; i < t.size(); i++){
		for (int j = 0; j < 5005; j++) if (dp[i][j]){
			for (int s = 0; s <= t[i]; s++){
				add(dp[i + 1][j + s], mult(dp[i][j], mult(cnk(s, t[i]), mult(fac[s], cnk(s, t[i])))));
			}
		}
	}

	for (int i = 0; i < 5005; i++){
		dp[t.size()][i] = mult(dp[t.size()][i], fac[n - i - 1]);
		if (i % 2 == 0) ans = sum(ans, dp[t.size()][i]);
		else ans = sub(ans, dp[t.size()][i]);
	}

	cout << ans;
}       
```