#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=5e3+10,mod=1e9+7;
int n,size[maxn],maxd[maxn],rt;
ll dp[maxn],ans;
vector<int> g[maxn];
ll fac[maxn],c[maxn][maxn];

void dfs1(int pos,int fa){
	size[pos]=1;
	for(int i=0;i<g[pos].size();++i)
		if(g[pos][i]!=fa){
			dfs1(g[pos][i],pos);
			size[pos]+=size[g[pos][i]];
			maxd[pos]=max(maxd[pos],size[g[pos][i]]);
		}
	maxd[pos]=max(maxd[pos],n-size[pos]);
}

int main(){
	fac[0]=1;
	for(int i=1;i<maxn;++i)
		fac[i]=fac[i-1]*i%mod;
	for(int i=0;i<maxn;++i){
		c[i][0]=1;
		for(int j=1;j<=i;++j)
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
	}
	cin>>n;
	for(int i=1,u,v;i<n;++i){
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs1(1,0);
	for(int i=1;i<=n;++i)
		if(maxd[i]<=n/2)
			if(rt){
				printf("%lld\n",fac[n/2]*fac[n/2]%mod);
				return 0;
			}
			else
				rt=i;
	dfs1(rt,0);
	dp[0]=1;
	for(int i=0;i<g[rt].size();++i){
		int now=size[g[rt][i]];
		for(int i=n;i;--i)
			for(int j=i-1;~j&&i-j<=now;--j)
				(dp[i]+=dp[j]*c[now][i-j]%mod*c[now][i-j]%mod*fac[i-j])%=mod;
	}
	for(int i=0;i<=n;++i)
		(ans+=(i&1?-1:1)*dp[i]*fac[n-i])%=mod;
	printf("%lld\n",(ans+mod)%mod);
	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>
using namespace std;

typedef long long ll;
const int maxn=5e3+10,mod=1e9+7;
int n,size[maxn],maxd[maxn],rt;
ll dp[maxn],ans;
vector<int> g[maxn];
ll fac[maxn],c[maxn][maxn];

void dfs1(int pos,int fa){
	size[pos]=1;
	for(int i=0;i<g[pos].size();++i)
		if(g[pos][i]!=fa){
			dfs1(g[pos][i],pos);
			size[pos]+=size[g[pos][i]];
			maxd[pos]=max(maxd[pos],size[g[pos][i]]);
		}
	maxd[pos]=max(maxd[pos],n-size[pos]);
}

int main(){
	fac[0]=1;
	for(int i=1;i<maxn;++i)
		fac[i]=fac[i-1]*i%mod;
	for(int i=0;i<maxn;++i){
		c[i][0]=1;
		for(int j=1;j<=i;++j)
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
	}
	cin>>n;
	for(int i=1,u,v;i<n;++i){
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs1(1,0);
	for(int i=1;i<=n;++i)
		if(maxd[i]<=n/2)
			if(rt){
				printf("%lld\n",fac[n/2]*fac[n/2]%mod);
				return 0;
			}
			else
				rt=i;
	dfs1(rt,0);
	dp[0]=1;
	for(int i=0;i<g[rt].size();++i){
		int now=size[g[rt][i]];
		for(int i=n;i;--i)
			for(int j=i-1;~j&&i-j<=now;--j)
				(dp[i]+=dp[j]*c[now][i-j]%mod*c[now][i-j]%mod*fac[i-j])%=mod;
	}
	for(int i=0;i<=n;++i)
		(ans+=(i&1?-1:1)*dp[i]*fac[n-i])%=mod;
	printf("%lld\n",(ans+mod)%mod);
	return 0;
}
```