#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1000000007LL;
void  find_centroids(int v, int p, vector<vector<int>> &G, vector<int> &subtree_size, vector<int> &centroids) {
	int N = G.size();
	bool isCentroid = 1;
	for (int to : G[v]) {
		if (to == p) continue;
		find_centroids(to, v, G, subtree_size, centroids);
		if (subtree_size[to] > N / 2) isCentroid = 0;
	}
	if (N - subtree_size[v] > N / 2) isCentroid = 0;
	if (isCentroid) centroids.push_back(v);
}
void calc_subtree_size(int v, int p, vector<vector<int>> &G, vector<int> &subtree_size) {
	subtree_size[v] = 1;
	for (int to : G[v]) {
		if (to == p) continue;
		calc_subtree_size(to, v, G, subtree_size);
		subtree_size[v] += subtree_size[to];
	}
}
ll fact[5001];
ll inv_fact[5001];
ll mod_pow(ll a, ll b) {
	if (b == 0) return 1;
	if (b % 2 == 0) {
		ll x = mod_pow(a, b / 2);
		return (x*x) % MOD;
	}
	return (a*mod_pow(a, b - 1)) % MOD;
}
ll comb(ll n, ll k) {
	if (n < k) return 0;
	ll ret = fact[n];
	(ret *= inv_fact[k]) %= MOD;
	(ret *= inv_fact[n - k]) %= MOD;
	return ret;
}
ll dp[5001][5001];
int main() {
	int N;
	cin >> N;
	fact[0] = inv_fact[0] = 1;
	for (int i = 1; i <= N; i++) {
		fact[i] = (fact[i - 1] * i) % MOD;
		inv_fact[i] = (inv_fact[i - 1] * mod_pow(i, MOD - 2)) % MOD;
	}
	vector<vector<int>> G(N, vector<int>());
	vector<int> centroids;
	vector<int> subtree_size(N);
	for (int i = 0; i < N - 1; i++) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	calc_subtree_size(0, -1, G, subtree_size);
	find_centroids(0, -1, G, subtree_size, centroids);
	if (centroids.size() == 2) {
		cout << (fact[N / 2] * fact[N / 2]) % MOD << endl;
		return 0;
	}
	int c = centroids[0];
	calc_subtree_size(c, -1, G, subtree_size);
	vector<int> T;
	for (int to : G[c]) T.push_back(subtree_size[to]);
	dp[0][0] = 1;
	for (int i = 1; i <= T.size(); i++) {
		for (int j = 0; j <= N; j++) {
			for (int k = 0; k <= T[i - 1]; k++) {
				if (j + k > N) break;
				ll add = dp[i - 1][j];
				ll t = comb(T[i - 1], k);
				t = (t*t) % MOD;
				(add *= t) %= MOD;
				(add *= fact[k]) %= MOD;
				(dp[i][j + k] += add) %= MOD;
			}
		}
	}
	ll ans = 0;
	ll k = 1;
	for (int i = 0; i <= N - 1; i++) {
		ll add = fact[N - i];
		(add *= dp[T.size()][i]) %= MOD;
		(add *= k) %= MOD;
		(ans += add) %= MOD;
		(k *= MOD - 1) %= MOD;
	}
	cout << ans << endl;
}

### Prompt

Please formulate 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 "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1000000007LL;
void  find_centroids(int v, int p, vector<vector<int>> &G, vector<int> &subtree_size, vector<int> &centroids) {
	int N = G.size();
	bool isCentroid = 1;
	for (int to : G[v]) {
		if (to == p) continue;
		find_centroids(to, v, G, subtree_size, centroids);
		if (subtree_size[to] > N / 2) isCentroid = 0;
	}
	if (N - subtree_size[v] > N / 2) isCentroid = 0;
	if (isCentroid) centroids.push_back(v);
}
void calc_subtree_size(int v, int p, vector<vector<int>> &G, vector<int> &subtree_size) {
	subtree_size[v] = 1;
	for (int to : G[v]) {
		if (to == p) continue;
		calc_subtree_size(to, v, G, subtree_size);
		subtree_size[v] += subtree_size[to];
	}
}
ll fact[5001];
ll inv_fact[5001];
ll mod_pow(ll a, ll b) {
	if (b == 0) return 1;
	if (b % 2 == 0) {
		ll x = mod_pow(a, b / 2);
		return (x*x) % MOD;
	}
	return (a*mod_pow(a, b - 1)) % MOD;
}
ll comb(ll n, ll k) {
	if (n < k) return 0;
	ll ret = fact[n];
	(ret *= inv_fact[k]) %= MOD;
	(ret *= inv_fact[n - k]) %= MOD;
	return ret;
}
ll dp[5001][5001];
int main() {
	int N;
	cin >> N;
	fact[0] = inv_fact[0] = 1;
	for (int i = 1; i <= N; i++) {
		fact[i] = (fact[i - 1] * i) % MOD;
		inv_fact[i] = (inv_fact[i - 1] * mod_pow(i, MOD - 2)) % MOD;
	}
	vector<vector<int>> G(N, vector<int>());
	vector<int> centroids;
	vector<int> subtree_size(N);
	for (int i = 0; i < N - 1; i++) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	calc_subtree_size(0, -1, G, subtree_size);
	find_centroids(0, -1, G, subtree_size, centroids);
	if (centroids.size() == 2) {
		cout << (fact[N / 2] * fact[N / 2]) % MOD << endl;
		return 0;
	}
	int c = centroids[0];
	calc_subtree_size(c, -1, G, subtree_size);
	vector<int> T;
	for (int to : G[c]) T.push_back(subtree_size[to]);
	dp[0][0] = 1;
	for (int i = 1; i <= T.size(); i++) {
		for (int j = 0; j <= N; j++) {
			for (int k = 0; k <= T[i - 1]; k++) {
				if (j + k > N) break;
				ll add = dp[i - 1][j];
				ll t = comb(T[i - 1], k);
				t = (t*t) % MOD;
				(add *= t) %= MOD;
				(add *= fact[k]) %= MOD;
				(dp[i][j + k] += add) %= MOD;
			}
		}
	}
	ll ans = 0;
	ll k = 1;
	for (int i = 0; i <= N - 1; i++) {
		ll add = fact[N - i];
		(add *= dp[T.size()][i]) %= MOD;
		(add *= k) %= MOD;
		(ans += add) %= MOD;
		(k *= MOD - 1) %= MOD;
	}
	cout << ans << endl;
}

```