#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define pb push_back

int n;
vector<int> e[5010];
const ll mod=int(1e9)+7;

int szh[5010][5010];
int sz(int x, int p){
	if(szh[x][p]) return szh[x][p];
	int ret=1;
	for(int y:e[x]) if(p != y) ret += sz(y, x);
	return szh[x][p]=ret;
}

int a[5010], an;

ll fact[5010];
ll finv[5010];
ll comb(ll a, ll b){
	return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
ll perm(ll a, ll b){
	return fact[a]*finv[a-b]%mod;
}

ll dp[5010];

ll Work(){
	dp[0] = 1;
	fill(dp+1, dp+accumulate(a+1, a+an+1, 0)+1, 0);
	int ps = 0;
	for(int i=1; i<=an; ++i){
		int ai=a[i];
		for(int j=ps; 0<=j; --j){
			for(int use=1; use<=ai; ++use){
				(dp[j+use] += dp[j] * comb(ai, use) % mod * perm(ai, use) % mod) %= mod;
			}
		}
		ps += ai;
	}
	ll ret = fact[ps];
	for(int i=1; i<=ps; ++i){
		if(i&1)
			(ret += (mod - dp[i] * fact[ps-i] % mod)) %= mod;
		else
			(ret += dp[i]*fact[ps-i]) %= mod;
	}
	return ret;
}

int main(){
	scanf("%d", &n);
	
	fact[0]=1; finv[n]=1;
	for(int i=1; i<=n; ++i) fact[i]=i*fact[i-1]%mod;
	for(ll b=fact[n], e=mod-2; e; (b*=b)%=mod, e/=2) if(e&1) (finv[n]*=b)%=mod;
	for(int i=n; 1<=i; --i) finv[i-1]=finv[i]*i%mod;

	for(int a,b,i=1; i<n; ++i){
		scanf("%d%d", &a, &b); e[a].pb(b); e[b].pb(a);
	}
	int p=1;
	while(true){
		bool flg=0;
		for(int q:e[p]){
			int A=sz(p, q), B=sz(q, p);
			if(A < B){
				p = q;
				flg=1;
				break;
			} else if(A == B){
				ll ans = 1;
				for(int i=1; i<=n/2; ++i){
					(ans *= i) %= mod;
				}
				(ans *= ans) %= mod;
				printf("%lld\n", ans);
				return 0;
			}
		}
		if(!flg) break;
	}
	//printf("Centroid %d\n", p);
	for(int x:e[p]) a[++an] = sz(x, p);
	ll ans = Work();
	a[++an] = 1;
	(ans += Work()) %= mod;
	printf("%lld\n", ans);
	return 0;
}

### 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;
using ll=long long;
#define pb push_back

int n;
vector<int> e[5010];
const ll mod=int(1e9)+7;

int szh[5010][5010];
int sz(int x, int p){
	if(szh[x][p]) return szh[x][p];
	int ret=1;
	for(int y:e[x]) if(p != y) ret += sz(y, x);
	return szh[x][p]=ret;
}

int a[5010], an;

ll fact[5010];
ll finv[5010];
ll comb(ll a, ll b){
	return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
ll perm(ll a, ll b){
	return fact[a]*finv[a-b]%mod;
}

ll dp[5010];

ll Work(){
	dp[0] = 1;
	fill(dp+1, dp+accumulate(a+1, a+an+1, 0)+1, 0);
	int ps = 0;
	for(int i=1; i<=an; ++i){
		int ai=a[i];
		for(int j=ps; 0<=j; --j){
			for(int use=1; use<=ai; ++use){
				(dp[j+use] += dp[j] * comb(ai, use) % mod * perm(ai, use) % mod) %= mod;
			}
		}
		ps += ai;
	}
	ll ret = fact[ps];
	for(int i=1; i<=ps; ++i){
		if(i&1)
			(ret += (mod - dp[i] * fact[ps-i] % mod)) %= mod;
		else
			(ret += dp[i]*fact[ps-i]) %= mod;
	}
	return ret;
}

int main(){
	scanf("%d", &n);
	
	fact[0]=1; finv[n]=1;
	for(int i=1; i<=n; ++i) fact[i]=i*fact[i-1]%mod;
	for(ll b=fact[n], e=mod-2; e; (b*=b)%=mod, e/=2) if(e&1) (finv[n]*=b)%=mod;
	for(int i=n; 1<=i; --i) finv[i-1]=finv[i]*i%mod;

	for(int a,b,i=1; i<n; ++i){
		scanf("%d%d", &a, &b); e[a].pb(b); e[b].pb(a);
	}
	int p=1;
	while(true){
		bool flg=0;
		for(int q:e[p]){
			int A=sz(p, q), B=sz(q, p);
			if(A < B){
				p = q;
				flg=1;
				break;
			} else if(A == B){
				ll ans = 1;
				for(int i=1; i<=n/2; ++i){
					(ans *= i) %= mod;
				}
				(ans *= ans) %= mod;
				printf("%lld\n", ans);
				return 0;
			}
		}
		if(!flg) break;
	}
	//printf("Centroid %d\n", p);
	for(int x:e[p]) a[++an] = sz(x, p);
	ll ans = Work();
	a[++an] = 1;
	(ans += Work()) %= mod;
	printf("%lld\n", ans);
	return 0;
}

```