#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
const int MAXN = 5005;
const int mod = 1e9 + 7;

lint ipow(lint x, lint p){
	lint ret = 1, piv = x % mod;
	while(p){
		if(p&1) ret *= piv;
		piv *= piv;
		ret %= mod;
		piv %= mod;
		p >>= 1;
	}
	return ret % mod;
}
typedef pair<int, int> pi;

vector<int> gph[MAXN];
int sz[MAXN], msz[MAXN];

void dfs(int x, int p){
	sz[x] = 1;
	for(auto &i : gph[x]){
		if(i != p){
			dfs(i, x);
			sz[x] += sz[i];
			msz[x] = max(msz[x], sz[i]);
		}
	}
}

int cnt[MAXN];
int n, c;

void dfs2(int x, int p, int c){
	cnt[c]++;
	for(auto &i : gph[x]){
		if(i != p){
			dfs2(i, x, c);
		}
	}
}

int dp[MAXN][MAXN];
lint fact[MAXN], invf[MAXN];

int solve(int y, int i){
	lint ans = (fact[y] * invf[y - i] % mod) * (fact[y] * invf[y - i] % mod);
	ans %= mod;
	ans *= invf[i];
	ans %= mod;
	if(i % 2 == 1) ans = (mod - ans) % mod;
	return ans;
}

int f(int x, int y){
	if(x == c+1) return fact[y];
	if(~dp[x][y]) return dp[x][y];
	lint ret = f(x+1, y);
	for(int i=1; i<=cnt[x]; i++){
		ret += 1ll * f(x+1, y-i) * solve(cnt[x], i) % mod;
		ret %= mod;
	}
	return dp[x][y] = ret;
}

void solve(int r){
	fact[0] = 1;
	for(int i=1; i<=n; i++) fact[i] = 1ll * i * fact[i-1] % mod;
	for(int i=0; i<=n; i++) invf[i] = ipow(fact[i], mod - 2);
	for(auto &i : gph[r]){
		dfs2(i, r, ++c);
	}
	memset(dp, -1, sizeof(dp));
	printf("%d\n", f(1, n));
}

int main(){
	scanf("%d",&n);
	for(int i=0; i<n-1; i++){
		int s, e;
		scanf("%d %d",&s,&e);
		gph[s].push_back(e);
		gph[e].push_back(s);
	}
	dfs(1, 0);
	pi cen(1e9, 0);
	for(int i=1; i<=n; i++){
		int cur = max(msz[i], n - sz[i]);
		cen = min(cen, pi(cur, i));
	}
	solve(cen.second);
}

### Prompt

Please provide a cpp coded solution 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;
typedef long long lint;
const int MAXN = 5005;
const int mod = 1e9 + 7;

lint ipow(lint x, lint p){
	lint ret = 1, piv = x % mod;
	while(p){
		if(p&1) ret *= piv;
		piv *= piv;
		ret %= mod;
		piv %= mod;
		p >>= 1;
	}
	return ret % mod;
}
typedef pair<int, int> pi;

vector<int> gph[MAXN];
int sz[MAXN], msz[MAXN];

void dfs(int x, int p){
	sz[x] = 1;
	for(auto &i : gph[x]){
		if(i != p){
			dfs(i, x);
			sz[x] += sz[i];
			msz[x] = max(msz[x], sz[i]);
		}
	}
}

int cnt[MAXN];
int n, c;

void dfs2(int x, int p, int c){
	cnt[c]++;
	for(auto &i : gph[x]){
		if(i != p){
			dfs2(i, x, c);
		}
	}
}

int dp[MAXN][MAXN];
lint fact[MAXN], invf[MAXN];

int solve(int y, int i){
	lint ans = (fact[y] * invf[y - i] % mod) * (fact[y] * invf[y - i] % mod);
	ans %= mod;
	ans *= invf[i];
	ans %= mod;
	if(i % 2 == 1) ans = (mod - ans) % mod;
	return ans;
}

int f(int x, int y){
	if(x == c+1) return fact[y];
	if(~dp[x][y]) return dp[x][y];
	lint ret = f(x+1, y);
	for(int i=1; i<=cnt[x]; i++){
		ret += 1ll * f(x+1, y-i) * solve(cnt[x], i) % mod;
		ret %= mod;
	}
	return dp[x][y] = ret;
}

void solve(int r){
	fact[0] = 1;
	for(int i=1; i<=n; i++) fact[i] = 1ll * i * fact[i-1] % mod;
	for(int i=0; i<=n; i++) invf[i] = ipow(fact[i], mod - 2);
	for(auto &i : gph[r]){
		dfs2(i, r, ++c);
	}
	memset(dp, -1, sizeof(dp));
	printf("%d\n", f(1, n));
}

int main(){
	scanf("%d",&n);
	for(int i=0; i<n-1; i++){
		int s, e;
		scanf("%d %d",&s,&e);
		gph[s].push_back(e);
		gph[e].push_back(s);
	}
	dfs(1, 0);
	pi cen(1e9, 0);
	for(int i=1; i<=n; i++){
		int cur = max(msz[i], n - sz[i]);
		cen = min(cen, pi(cur, i));
	}
	solve(cen.second);
}

```