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

#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl

typedef long long ll;
#define int ll
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
const int inf = 1000000001;
const ll INF = 2e18;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };



class CentroidDecomposition {
public:
	int n; //頂点数
	vii G; //グラフの隣接リスト表現
	vector<bool> isused; //その頂点がすでに分割に使われているか
	vi subtreesize; //部分木のサイズ,更新される
	vi parent;
	vi centroid; //重心が後ろに追加されていく
	vector<char> ans;

	CentroidDecomposition(int n) : n(n) {
		G.resize(n); isused.resize(n);
		subtreesize.resize(n); parent.resize(n);
		ans.resize(n);
	}

	void add_edge(int u, int v) {
		G[u].push_back(v); G[v].push_back(u);
	}

	int search_centroid(int now, int par, int size) {
		subtreesize[now] = 1;
		parent[now] = par;
		bool iscentroid = true;
		for (int i = 0; i < G[now].size(); i++) {
			int child = G[now][i];
			if (child == par) continue;
			if (isused[child]) continue;
			int child_size = search_centroid(child, now, size);
			if (child_size > size / 2) iscentroid = false;
			subtreesize[now] += child_size;
		}
		if (size - subtreesize[now] > size / 2) {
			iscentroid = false;
		}
		if (iscentroid) {
			centroid.push_back(now);
		}
		return subtreesize[now];
	}

	//問題によって変わる
	void solve(int root, char c, int size) {
		search_centroid(root, -1, size);
		int cent = centroid.back();
		isused[cent] = true;
		ans[cent] = c;
		rep(i, G[cent].size()) {
			int ch = G[cent][i];
			if (isused[ch]) {
				continue;
			}
			if (parent[ch] == cent) {
				solve(ch, c + 1, subtreesize[ch]);
			}
			else {
				solve(ch, c + 1, size - subtreesize[cent]);
			}
		}
		return;
	}

	int dfs(int now, int parent) {
		int cnt = 1;
		rep(i, G[now].size()) {
			int ch = G[now][i];
			if (ch == parent) {
				continue;
			}
			cnt += dfs(ch, now);
		}
		return cnt;
	}


};

vll dp(5151, vl(5151, 0));

signed main() {
	int n;
	cin >> n;
	vl fact(n + 1);
	fact[0] = 1;
	rep1(i, n) {
		fact[i] = (ll)i * fact[i - 1] % MOD;
	}
	/*
	rep(i, n) {
	cout << fact[i] << " ";
	}
	cout << endl;
	//*/
	vll C(n + 1, vl(n + 1));
	C[0][0] = 1;
	rep1(i, n) {
		rep(j, i + 1) {
			if (j == 0 || j == i) {
				C[i][j] = 1;
			}
			else {
				C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
			}
		}
	}
	/*
	rep(i, n) {
	rep(j, i + 1) {
	cout << C[i][j] << " ";
	}
	cout << endl;
	}
	cout << endl;
	//*/
	CentroidDecomposition tree(n);
	rep(i, n - 1) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		tree.add_edge(x, y);
	}
	tree.search_centroid(0, -1, n);
	if (tree.centroid.size() == 2) {
		cout << fact[n / 2] * fact[n / 2] % MOD << endl;
		return 0;
	}
	vl num;
	int cent = tree.centroid[0];
	rep(i, tree.G[cent].size()) {
		int ch = tree.G[cent][i];
		num.push_back(tree.dfs(ch, cent));
	}
	dp[0][0] = 1;
	rep(i, num.size()) {
		rep(j, n + 1) {
			if (dp[i][j] == 0) {
				continue;
			}
			rep(k, num[i] + 1) {
				if (j + k > n) {
					break;
				}
				(dp[i + 1][j + k] += dp[i][j] * C[num[i]][k] % MOD * C[num[i]][k] % MOD * fact[k] % MOD) %= MOD;
			}
		}
	}
	ll ans = 0, sgn = 1;
	rep(i, n + 1) {
		(ans += sgn*fact[n - i] * dp[num.size()][i] % MOD) % MOD;
		sgn *= -1;
	}
	while (ans < 0) {
		ans += MOD;
	}
	cout << (ans + MOD) % MOD << endl;
}
### Prompt

Your challenge is to write 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;

#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl

typedef long long ll;
#define int ll
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
const int inf = 1000000001;
const ll INF = 2e18;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };



class CentroidDecomposition {
public:
	int n; //頂点数
	vii G; //グラフの隣接リスト表現
	vector<bool> isused; //その頂点がすでに分割に使われているか
	vi subtreesize; //部分木のサイズ,更新される
	vi parent;
	vi centroid; //重心が後ろに追加されていく
	vector<char> ans;

	CentroidDecomposition(int n) : n(n) {
		G.resize(n); isused.resize(n);
		subtreesize.resize(n); parent.resize(n);
		ans.resize(n);
	}

	void add_edge(int u, int v) {
		G[u].push_back(v); G[v].push_back(u);
	}

	int search_centroid(int now, int par, int size) {
		subtreesize[now] = 1;
		parent[now] = par;
		bool iscentroid = true;
		for (int i = 0; i < G[now].size(); i++) {
			int child = G[now][i];
			if (child == par) continue;
			if (isused[child]) continue;
			int child_size = search_centroid(child, now, size);
			if (child_size > size / 2) iscentroid = false;
			subtreesize[now] += child_size;
		}
		if (size - subtreesize[now] > size / 2) {
			iscentroid = false;
		}
		if (iscentroid) {
			centroid.push_back(now);
		}
		return subtreesize[now];
	}

	//問題によって変わる
	void solve(int root, char c, int size) {
		search_centroid(root, -1, size);
		int cent = centroid.back();
		isused[cent] = true;
		ans[cent] = c;
		rep(i, G[cent].size()) {
			int ch = G[cent][i];
			if (isused[ch]) {
				continue;
			}
			if (parent[ch] == cent) {
				solve(ch, c + 1, subtreesize[ch]);
			}
			else {
				solve(ch, c + 1, size - subtreesize[cent]);
			}
		}
		return;
	}

	int dfs(int now, int parent) {
		int cnt = 1;
		rep(i, G[now].size()) {
			int ch = G[now][i];
			if (ch == parent) {
				continue;
			}
			cnt += dfs(ch, now);
		}
		return cnt;
	}


};

vll dp(5151, vl(5151, 0));

signed main() {
	int n;
	cin >> n;
	vl fact(n + 1);
	fact[0] = 1;
	rep1(i, n) {
		fact[i] = (ll)i * fact[i - 1] % MOD;
	}
	/*
	rep(i, n) {
	cout << fact[i] << " ";
	}
	cout << endl;
	//*/
	vll C(n + 1, vl(n + 1));
	C[0][0] = 1;
	rep1(i, n) {
		rep(j, i + 1) {
			if (j == 0 || j == i) {
				C[i][j] = 1;
			}
			else {
				C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
			}
		}
	}
	/*
	rep(i, n) {
	rep(j, i + 1) {
	cout << C[i][j] << " ";
	}
	cout << endl;
	}
	cout << endl;
	//*/
	CentroidDecomposition tree(n);
	rep(i, n - 1) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		tree.add_edge(x, y);
	}
	tree.search_centroid(0, -1, n);
	if (tree.centroid.size() == 2) {
		cout << fact[n / 2] * fact[n / 2] % MOD << endl;
		return 0;
	}
	vl num;
	int cent = tree.centroid[0];
	rep(i, tree.G[cent].size()) {
		int ch = tree.G[cent][i];
		num.push_back(tree.dfs(ch, cent));
	}
	dp[0][0] = 1;
	rep(i, num.size()) {
		rep(j, n + 1) {
			if (dp[i][j] == 0) {
				continue;
			}
			rep(k, num[i] + 1) {
				if (j + k > n) {
					break;
				}
				(dp[i + 1][j + k] += dp[i][j] * C[num[i]][k] % MOD * C[num[i]][k] % MOD * fact[k] % MOD) %= MOD;
			}
		}
	}
	ll ans = 0, sgn = 1;
	rep(i, n + 1) {
		(ans += sgn*fact[n - i] * dp[num.size()][i] % MOD) % MOD;
		sgn *= -1;
	}
	while (ans < 0) {
		ans += MOD;
	}
	cout << (ans + MOD) % MOD << endl;
}
```