#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<queue>
#include<stack>
#include<functional>
using namespace std;
int p = 1000000007;
#define int long long
#define vel vector<long long>
#define vvel vector<vel>
#define rep(i,n) for(long long i=0;i<n;i++)
#define sor(v) sort(v.begin(),v.end())
#define mmax(a,b) a=max(a,b)
#define mmin(a,b) a=min(a,b)
#define mkp make_pair
#define pin pair<int,int>
#define V vector
int kai_size = 5001;
vel kai(kai_size, 1);
vel kai2;
vel ink(kai_size, 1);
vel ink2;
const int MAX_V = 5300;  // ツリーのサイズのありうる最大値

int n;  // ツリーのサイズ
vvel tree;  // ツリーを隣接リスト形式のグラフ構造で表したもの

vel sizeSubtree(MAX_V,1);  // sizeSubtree[v] := v を根とする部分ツリーのサイズ

vel dis(int mid1, vvel &way) {
	int n = way.size();
	vel dist(n, -1); dist[mid1] = 0;
	queue<int> q;
	q.push(mid1);
	while (!q.empty()) {
		int st = q.front(); q.pop();
		rep(i, way[st].size()) {
			int to = way[st][i];
			if (dist[to] == -1) {
				dist[to] = dist[st] + 1;
				q.push(to);
			}
		}
	}
	return dist;
}
int FindCentroids() {
	vel dist = dis(0,tree);
	vvel list_d(n);
	rep(i, n) {
		list_d[dist[i]].push_back(i);
	}
	for (int i = n - 1; i > 0; i--){
		for (auto v : list_d[i]) {
			for (auto nex : tree[v]) {
				if (dist[nex] > dist[v]) {
					sizeSubtree[v] += sizeSubtree[nex];
				}
			}
		}
	}
	rep(i, n) {
		bool is_center = true;
		for (auto ch : tree[i]) {
			if (dist[ch] > dist[i]) {
				if (sizeSubtree[ch] > n / 2) { is_center = false; }
			}
		}
		if (n - sizeSubtree[i] > n / 2) { is_center = false; }
		if (is_center) { return i; }
	}
	return 0;
}
int size_tree(int back, int now, vvel way) {
	int ans = 1;
	rep(j, way[now].size()) {
		int nex = way[now][j];
		if (nex != back) {
			ans += size_tree(now, nex, way);
		}
	}
	return ans;
}
int ru(int a, int r) {
	if (r == 0) { return 1; }
	int ans = ru(a, r / 2);
	ans *= ans; ans %= p;
	if (r % 2 == 1) { ans *= a; }
	return ans % p;
}
int inv(int a) {
	return ru(a, p - 2);
}
void make_kai() {
	kai2 = kai; ink2 = ink;
	rep(i, kai_size - 1) {
		kai[i + 1] = (kai[i] * (i + 1)) % p;
		kai2[i + 1] = kai[i + 1] * kai[i + 1];
		kai2[i + 1] %= p;
	}
	rep(i, kai_size) {
		ink[i] = inv(kai[i]);
		ink2[i] = ink[i] * ink[i];
		ink2[i] %= p;
	}
}
int RE() {
	vel v(3, 2);
	return v.at(4);
}
int comper(int n, int r) {
	int ans = kai2[n] * ink2[n - r];
	ans %= p;
	ans *= ink[r];
	return ans % p;
}
void pl(int &a, int b) {
	a += b; a %= p;
}
signed main() {
	make_kai();
	cin >> n;
	vel x(n), y(n);
	vvel way(n);
	rep(i, n - 1) {
		cin >> x[i] >> y[i]; x[i]--; y[i]--;
		way[x[i]].push_back(y[i]);
		way[y[i]].push_back(x[i]);
	}
	tree = way;
	int g = FindCentroids();
	vel dist = dis(g, tree);
	vvel list_d(n);
	rep(i, n) {
		list_d[dist[i]].push_back(i);
	}
	sizeSubtree = vel(n, 1);
	for (int i = n - 1; i > 0; i--) {
		for (auto v : list_d[i]) {
			for (auto nex : tree[v]) {
				if (dist[nex] > dist[v]) {
					sizeSubtree[v] += sizeSubtree[nex];
				}
			}
		}
	}
	vel sub(way[g].size());
	rep(i, way[g].size()) {
		sub[i]=sizeSubtree[way[g][i]];
	}
	sor(sub);
	int sz = way[g].size();
	vvel dp(2,vel(5010,0));
	dp[0][0] = 1;
	int sum = 0;
	rep(i, sz) {
		int now = i % 2;
		int nex = (i + 1) % 2;
		for (int j = 0; j <= sum; j++) {
			rep(k, sub[i] + 1) {
				int plus = dp[now][j] * comper(sub[i], k);
				pl(dp[nex][j + k], plus);
			}
			dp[now][j] = 0;
		}
		sum += sub[i];
	}
	int ans = 0;
	int bi = 1;
	rep(i, n) {
		int plus = dp[sz%2][i] * kai[n - i];
		pl(ans, plus*bi);
		bi *= -1;
	}
	ans += p; ans %= p;
	cout << ans << endl;
	return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<queue>
#include<stack>
#include<functional>
using namespace std;
int p = 1000000007;
#define int long long
#define vel vector<long long>
#define vvel vector<vel>
#define rep(i,n) for(long long i=0;i<n;i++)
#define sor(v) sort(v.begin(),v.end())
#define mmax(a,b) a=max(a,b)
#define mmin(a,b) a=min(a,b)
#define mkp make_pair
#define pin pair<int,int>
#define V vector
int kai_size = 5001;
vel kai(kai_size, 1);
vel kai2;
vel ink(kai_size, 1);
vel ink2;
const int MAX_V = 5300;  // ツリーのサイズのありうる最大値

int n;  // ツリーのサイズ
vvel tree;  // ツリーを隣接リスト形式のグラフ構造で表したもの

vel sizeSubtree(MAX_V,1);  // sizeSubtree[v] := v を根とする部分ツリーのサイズ

vel dis(int mid1, vvel &way) {
	int n = way.size();
	vel dist(n, -1); dist[mid1] = 0;
	queue<int> q;
	q.push(mid1);
	while (!q.empty()) {
		int st = q.front(); q.pop();
		rep(i, way[st].size()) {
			int to = way[st][i];
			if (dist[to] == -1) {
				dist[to] = dist[st] + 1;
				q.push(to);
			}
		}
	}
	return dist;
}
int FindCentroids() {
	vel dist = dis(0,tree);
	vvel list_d(n);
	rep(i, n) {
		list_d[dist[i]].push_back(i);
	}
	for (int i = n - 1; i > 0; i--){
		for (auto v : list_d[i]) {
			for (auto nex : tree[v]) {
				if (dist[nex] > dist[v]) {
					sizeSubtree[v] += sizeSubtree[nex];
				}
			}
		}
	}
	rep(i, n) {
		bool is_center = true;
		for (auto ch : tree[i]) {
			if (dist[ch] > dist[i]) {
				if (sizeSubtree[ch] > n / 2) { is_center = false; }
			}
		}
		if (n - sizeSubtree[i] > n / 2) { is_center = false; }
		if (is_center) { return i; }
	}
	return 0;
}
int size_tree(int back, int now, vvel way) {
	int ans = 1;
	rep(j, way[now].size()) {
		int nex = way[now][j];
		if (nex != back) {
			ans += size_tree(now, nex, way);
		}
	}
	return ans;
}
int ru(int a, int r) {
	if (r == 0) { return 1; }
	int ans = ru(a, r / 2);
	ans *= ans; ans %= p;
	if (r % 2 == 1) { ans *= a; }
	return ans % p;
}
int inv(int a) {
	return ru(a, p - 2);
}
void make_kai() {
	kai2 = kai; ink2 = ink;
	rep(i, kai_size - 1) {
		kai[i + 1] = (kai[i] * (i + 1)) % p;
		kai2[i + 1] = kai[i + 1] * kai[i + 1];
		kai2[i + 1] %= p;
	}
	rep(i, kai_size) {
		ink[i] = inv(kai[i]);
		ink2[i] = ink[i] * ink[i];
		ink2[i] %= p;
	}
}
int RE() {
	vel v(3, 2);
	return v.at(4);
}
int comper(int n, int r) {
	int ans = kai2[n] * ink2[n - r];
	ans %= p;
	ans *= ink[r];
	return ans % p;
}
void pl(int &a, int b) {
	a += b; a %= p;
}
signed main() {
	make_kai();
	cin >> n;
	vel x(n), y(n);
	vvel way(n);
	rep(i, n - 1) {
		cin >> x[i] >> y[i]; x[i]--; y[i]--;
		way[x[i]].push_back(y[i]);
		way[y[i]].push_back(x[i]);
	}
	tree = way;
	int g = FindCentroids();
	vel dist = dis(g, tree);
	vvel list_d(n);
	rep(i, n) {
		list_d[dist[i]].push_back(i);
	}
	sizeSubtree = vel(n, 1);
	for (int i = n - 1; i > 0; i--) {
		for (auto v : list_d[i]) {
			for (auto nex : tree[v]) {
				if (dist[nex] > dist[v]) {
					sizeSubtree[v] += sizeSubtree[nex];
				}
			}
		}
	}
	vel sub(way[g].size());
	rep(i, way[g].size()) {
		sub[i]=sizeSubtree[way[g][i]];
	}
	sor(sub);
	int sz = way[g].size();
	vvel dp(2,vel(5010,0));
	dp[0][0] = 1;
	int sum = 0;
	rep(i, sz) {
		int now = i % 2;
		int nex = (i + 1) % 2;
		for (int j = 0; j <= sum; j++) {
			rep(k, sub[i] + 1) {
				int plus = dp[now][j] * comper(sub[i], k);
				pl(dp[nex][j + k], plus);
			}
			dp[now][j] = 0;
		}
		sum += sub[i];
	}
	int ans = 0;
	int bi = 1;
	rep(i, n) {
		int plus = dp[sz%2][i] * kai[n - i];
		pl(ans, plus*bi);
		bi *= -1;
	}
	ans += p; ans %= p;
	cout << ans << endl;
	return 0;
}

```