#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n;
vector<int> G[5005];
P siz[5005];
int parent[5005];
ll fact[5005];

P dfs(int v,int p){
	P val=P(1,0);
	parent[v]=p;
	for(int i=0;i<G[v].size();i++){
		int nv=G[v][i];
		if(nv==p)continue;
		P tmp=dfs(G[v][i],v);
		val.first+=tmp.first;
		val.second=max(val.second,tmp.first);
	}
	val.second=max(val.second,n-val.first);
	return siz[v]=val;
}

ll extgcd(ll a,ll b,ll& x,ll& y){
	ll d=a;
	if(b!=0LL){
		d=extgcd(b,a%b,y,x);
		y-=(a/b)*x;
	}else{
		x=1;
		y=0;
	}
	return d;
}

ll mod_inverse(ll a,ll m){
	ll x,y;
	extgcd(a,m,x,y);
	return (m+x%m)%m;
}
ll mod_fact(ll n,ll p,ll& e){
	e=0;
	if(n==0)return 1;
	ll res=mod_fact(n/p,p,e);
	e+=n/p;
	if(n/p%2!=0){
		return res*(p-fact[n%p])%p;
	}
	return res*fact[n%p]%p;
}

ll mod_comb(ll n,ll k,ll p){
	if(n<0 || k<0 || n<k)return 0;
	ll e1,e2,e3;
	ll a1=mod_fact(n,p,e1),a2=mod_fact(k,p,e2),a3=mod_fact(n-k,p,e3);
	if(e1>e2+e3)return 0;
	return a1*mod_inverse(a2*a3%p,p)%p;
}

ll dp[5005][5005];
ll comb[5005][5005];

int main(void){
	fact[0]=1;
	comb[0][0]=1;
	for(int i=1;i<=5000;i++){
		for(int j=1;j<i;j++){
			comb[i][j]=(comb[i-1][j]+comb[i-1][j-1])%MOD;
		}
		comb[i][0]=1;
		comb[i][i]=1;
	}
	for(int i=1;i<=5000;i++){
		fact[i]=(ll)fact[i-1]*i%MOD;
	}
	scanf("%d",&n);
	for(int i=0;i<n-1;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		a--;
		b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	dfs(0,-1);
	int bs=0,cnt=1;
	for(int i=1;i<n;i++){
		if(siz[bs].second>siz[i].second){
			cnt=0;
			bs=i;
		}
		if(siz[bs].second==siz[i].second){
			cnt++;
		}
	}
	if(cnt==2){
		printf("%lld\n",fact[n/2]*fact[n/2]%MOD);
		return 0;
	}

	vector<int> vec;
	for(int i=0;i<G[bs].size();i++){
		int nv=G[bs][i];
		if(nv==parent[bs])continue;
		vec.push_back(siz[nv].first);
	}
	if(parent[bs]!=-1){
		vec.push_back(n-siz[bs].first);
	}
	dp[0][0]=1;
	int sum=0;
	for(int i=0;i<vec.size();i++){
		//printf("%d\n",vec[i]);
		int v=vec[i];
		for(int j=0;j<=sum;j++){
			for(int k=0;k<=v;k++){
				ll val=comb[v][k]*comb[v][k]%MOD*fact[k]%MOD;
				dp[i+1][j+k]+=dp[i][j]*val%MOD;
				dp[i+1][j+k]%=MOD;
			}
		}
		sum+=v;
	}
	ll ans=0;
	for(int i=0;i<=n;i++){
		ll val=dp[vec.size()][i];
		val=val*fact[n-i]%MOD;
		if(i%2==1)val=-val;
		ans+=val;
		if(ans<0)ans+=MOD;
		ans%=MOD;
	}
	printf("%lld\n",ans);
	return 0;
}
### Prompt

Please create a solution in CPP 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>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n;
vector<int> G[5005];
P siz[5005];
int parent[5005];
ll fact[5005];

P dfs(int v,int p){
	P val=P(1,0);
	parent[v]=p;
	for(int i=0;i<G[v].size();i++){
		int nv=G[v][i];
		if(nv==p)continue;
		P tmp=dfs(G[v][i],v);
		val.first+=tmp.first;
		val.second=max(val.second,tmp.first);
	}
	val.second=max(val.second,n-val.first);
	return siz[v]=val;
}

ll extgcd(ll a,ll b,ll& x,ll& y){
	ll d=a;
	if(b!=0LL){
		d=extgcd(b,a%b,y,x);
		y-=(a/b)*x;
	}else{
		x=1;
		y=0;
	}
	return d;
}

ll mod_inverse(ll a,ll m){
	ll x,y;
	extgcd(a,m,x,y);
	return (m+x%m)%m;
}
ll mod_fact(ll n,ll p,ll& e){
	e=0;
	if(n==0)return 1;
	ll res=mod_fact(n/p,p,e);
	e+=n/p;
	if(n/p%2!=0){
		return res*(p-fact[n%p])%p;
	}
	return res*fact[n%p]%p;
}

ll mod_comb(ll n,ll k,ll p){
	if(n<0 || k<0 || n<k)return 0;
	ll e1,e2,e3;
	ll a1=mod_fact(n,p,e1),a2=mod_fact(k,p,e2),a3=mod_fact(n-k,p,e3);
	if(e1>e2+e3)return 0;
	return a1*mod_inverse(a2*a3%p,p)%p;
}

ll dp[5005][5005];
ll comb[5005][5005];

int main(void){
	fact[0]=1;
	comb[0][0]=1;
	for(int i=1;i<=5000;i++){
		for(int j=1;j<i;j++){
			comb[i][j]=(comb[i-1][j]+comb[i-1][j-1])%MOD;
		}
		comb[i][0]=1;
		comb[i][i]=1;
	}
	for(int i=1;i<=5000;i++){
		fact[i]=(ll)fact[i-1]*i%MOD;
	}
	scanf("%d",&n);
	for(int i=0;i<n-1;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		a--;
		b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	dfs(0,-1);
	int bs=0,cnt=1;
	for(int i=1;i<n;i++){
		if(siz[bs].second>siz[i].second){
			cnt=0;
			bs=i;
		}
		if(siz[bs].second==siz[i].second){
			cnt++;
		}
	}
	if(cnt==2){
		printf("%lld\n",fact[n/2]*fact[n/2]%MOD);
		return 0;
	}

	vector<int> vec;
	for(int i=0;i<G[bs].size();i++){
		int nv=G[bs][i];
		if(nv==parent[bs])continue;
		vec.push_back(siz[nv].first);
	}
	if(parent[bs]!=-1){
		vec.push_back(n-siz[bs].first);
	}
	dp[0][0]=1;
	int sum=0;
	for(int i=0;i<vec.size();i++){
		//printf("%d\n",vec[i]);
		int v=vec[i];
		for(int j=0;j<=sum;j++){
			for(int k=0;k<=v;k++){
				ll val=comb[v][k]*comb[v][k]%MOD*fact[k]%MOD;
				dp[i+1][j+k]+=dp[i][j]*val%MOD;
				dp[i+1][j+k]%=MOD;
			}
		}
		sum+=v;
	}
	ll ans=0;
	for(int i=0;i<=n;i++){
		ll val=dp[vec.size()][i];
		val=val*fact[n-i]%MOD;
		if(i%2==1)val=-val;
		ans+=val;
		if(ans<0)ans+=MOD;
		ans%=MOD;
	}
	printf("%lld\n",ans);
	return 0;
}
```