#include<bits/stdc++.h>
using namespace std;
const int maxn=5010,mod=1e9+7;
typedef long long ll;
int n,cnt;
ll c[maxn][maxn],fac[maxn],f[maxn],g[maxn];
int sz[maxn],mx[maxn],rt[maxn],a[maxn];
vector<int> G[maxn];
void init_Binom(){
	c[0][0]=1;
	for(int i=0;i<=n;++i)c[i][0]=c[i][i]=1;
	for(int i=1;i<=n;++i)
		for(int j=1;j<i;++j){
			c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
		}
	fac[0]=1;
	for(int i=1;i<=n;++i){
		fac[i]=fac[i-1]*i%mod;
	}
}
ll C(int n,int m){
	if(n<0||m<0||n<m)return 0;
	return c[n][m];
}
void dfs(int u,int fa){
	sz[u]=1;mx[u]=0;
	for(auto v: G[u])if(v!=fa){
		dfs(v,u);
		sz[u]+=sz[v];
		mx[u]=max(mx[u],sz[v]);
	}
	mx[u]=max(mx[u],n-sz[u]);
	if(mx[u]<mx[rt[cnt]])rt[cnt=1]=u;
	else if(mx[u]==mx[rt[cnt]])rt[++cnt]=u;
}
void dfs2(int u,int fa){
	sz[u]=1;
	for(auto v: G[u])if(v!=fa){
		dfs2(v,u);
		sz[u]+=sz[v];
	}
}
void solve(){
	cin>>n;
	for(int i=1,u,v;i<n;++i){
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	init_Binom();
	mx[0]=INT_MAX;
	dfs(1,0);
	if(cnt==2){
		dfs2(rt[1],rt[2]);
		dfs2(rt[2],rt[1]);
		cout<<fac[sz[rt[2]]]*fac[sz[rt[1]]]%mod<<endl;
		exit(0);
	}
	cnt=0;dfs2(rt[1],0);
	for(auto v: G[rt[1]])a[++cnt]=sz[v];
	f[0]=1;
	int cur=0;
	for(int i=1;i<=cnt;++i){
		memset(g,0,sizeof(ll)*(cur+1));
		for(int j=0;j<=cur;++j)
			for(int k=0;k<=a[i];++k)
				(g[j+k]+=f[j]*C(a[i],k)%mod*C(a[i],k)%mod*fac[k]%mod)%=mod;
		cur+=a[i];
		memcpy(f,g,sizeof(ll)*(cur+1));
	}
	ll ans=0;
	for(int i=0;i<=n;++i){
		
		if(i&1)ans=(ans+mod-f[i]*fac[n-i]%mod)%mod;
		else (ans=ans+f[i]*fac[n-i]%mod)%mod;
	}
	cout<<ans<<endl;
}
int main(){
	solve();
	
	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;
const int maxn=5010,mod=1e9+7;
typedef long long ll;
int n,cnt;
ll c[maxn][maxn],fac[maxn],f[maxn],g[maxn];
int sz[maxn],mx[maxn],rt[maxn],a[maxn];
vector<int> G[maxn];
void init_Binom(){
	c[0][0]=1;
	for(int i=0;i<=n;++i)c[i][0]=c[i][i]=1;
	for(int i=1;i<=n;++i)
		for(int j=1;j<i;++j){
			c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
		}
	fac[0]=1;
	for(int i=1;i<=n;++i){
		fac[i]=fac[i-1]*i%mod;
	}
}
ll C(int n,int m){
	if(n<0||m<0||n<m)return 0;
	return c[n][m];
}
void dfs(int u,int fa){
	sz[u]=1;mx[u]=0;
	for(auto v: G[u])if(v!=fa){
		dfs(v,u);
		sz[u]+=sz[v];
		mx[u]=max(mx[u],sz[v]);
	}
	mx[u]=max(mx[u],n-sz[u]);
	if(mx[u]<mx[rt[cnt]])rt[cnt=1]=u;
	else if(mx[u]==mx[rt[cnt]])rt[++cnt]=u;
}
void dfs2(int u,int fa){
	sz[u]=1;
	for(auto v: G[u])if(v!=fa){
		dfs2(v,u);
		sz[u]+=sz[v];
	}
}
void solve(){
	cin>>n;
	for(int i=1,u,v;i<n;++i){
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	init_Binom();
	mx[0]=INT_MAX;
	dfs(1,0);
	if(cnt==2){
		dfs2(rt[1],rt[2]);
		dfs2(rt[2],rt[1]);
		cout<<fac[sz[rt[2]]]*fac[sz[rt[1]]]%mod<<endl;
		exit(0);
	}
	cnt=0;dfs2(rt[1],0);
	for(auto v: G[rt[1]])a[++cnt]=sz[v];
	f[0]=1;
	int cur=0;
	for(int i=1;i<=cnt;++i){
		memset(g,0,sizeof(ll)*(cur+1));
		for(int j=0;j<=cur;++j)
			for(int k=0;k<=a[i];++k)
				(g[j+k]+=f[j]*C(a[i],k)%mod*C(a[i],k)%mod*fac[k]%mod)%=mod;
		cur+=a[i];
		memcpy(f,g,sizeof(ll)*(cur+1));
	}
	ll ans=0;
	for(int i=0;i<=n;++i){
		
		if(i&1)ans=(ans+mod-f[i]*fac[n-i]%mod)%mod;
		else (ans=ans+f[i]*fac[n-i]%mod)%mod;
	}
	cout<<ans<<endl;
}
int main(){
	solve();
	
	return 0;
}
```