#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1e9 +7;
const ll inf=0x3f3f3f3f;
vector<int> son[5050];
int n,root;
ll ans;
int size[5050],deep[5050];
ll dis[5050],minn;
ll jc[5050],jc_ny[5050];
ll f[5050][5050];
ll Power(ll x,ll k)
{
	ll sss=1;
	while (k)
	{
		if (k%2) sss=sss*x%mod;
		x=x*x%mod;
		k/=2;
	}
	return sss;
}
ll ny(ll x){return Power(x,mod-2);}
ll C(int x,int y)
{
	if (y>x || y<0) return 0;
	if (y==x || y==0) return 1;
	ll sss=jc[x];
	sss=sss *jc_ny[x-y]%mod *jc_ny[y]%mod;
	return sss;
}
void init()
{
	jc[0]=1; jc_ny[0]=1;
	for (int i=1;i<=n;++i) jc[i]=jc[i-1]*i%mod,jc_ny[i]=ny(jc[i]);
}
void dfs(int x,int fa)
{
	deep[x]=deep[fa]+1;
	size[x]=1;
	int len=son[x].size();
	for (int i=0;i<len;++i)
	{
		int y=son[x][i];
		if (y==fa) continue;
		dfs(y,x);
		size[x]+=size[y];
	}
}
void get_dis(int x,int fa)
{
	int len=son[x].size();
	for (int i=0;i<len;++i)
	{
		int y=son[x][i];
		if (y==fa) continue;
		dis[y]=dis[x] -size[y] +(n-size[y]);
		get_dis(y,x);
	}
}
int main()
{
//	freopen("F.in","r",stdin);
//	freopen("F.out","w",stdout);

	scanf("%d",&n);
	init();
//	printf("%lld %lld\n",jc[3],jc_ny[3]);
//	printf("%lld\n",C(5,3));
	int x,y;
	for (int i=1;i<n;++i) 
	{
		scanf("%d%d",&x,&y);
		son[x].push_back(y);
		son[y].push_back(x);
	}
	deep[0]=-1;
	dfs(1,0);
	for (int i=1;i<=n;++i) dis[1]+=deep[i];
	get_dis(1,0);
//	for (int i=1;i<=n;++i) printf("%d ",size[i]);
//	printf("\n");
//	for (int i=1;i<=n;++i) printf("%lld ",dis[i]);
//	printf("\n");
	minn=inf;
	for (int i=1;i<=n;++i) minn=min(minn,dis[i]);
	for (int i=1;i<=n;++i) if (dis[i]==minn)
	{
		if (!root) root=i;
		else
		{
			printf("%lld\n",jc[n/2]*jc[n/2]%mod);
			return 0;
		}
	}
//	printf("root:%d\n",root);

	dfs(root,0);
	f[0][0]=1;
	int len=son[root].size(),sum=0;
	for (int i=1;i<=len;++i)
	{
		int y=son[root][i-1];
//		printf("%d : %d\n",y,size[y]);
		for (int j=0;j<=sum;++j) for (int k=0;k<=size[y];++k)
			(f[i][j+k]+= f[i-1][j]*C(size[y],k) %mod *C(size[y],k) %mod *jc[k]%mod )%=mod;
		
		sum+=size[y];
	}
	for (int i=0;i<=n;++i)
	{
		ll sss=f[len][i]*jc[n-i]%mod;
		if (i%2==0) ans+=sss;
		else ans-=sss;
	}
	printf("%lld\n",(ans%mod +mod)%mod);
	return 0;
}
### Prompt

Your task is to create a Cpp solution 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 ll long long
using namespace std;
const ll mod=1e9 +7;
const ll inf=0x3f3f3f3f;
vector<int> son[5050];
int n,root;
ll ans;
int size[5050],deep[5050];
ll dis[5050],minn;
ll jc[5050],jc_ny[5050];
ll f[5050][5050];
ll Power(ll x,ll k)
{
	ll sss=1;
	while (k)
	{
		if (k%2) sss=sss*x%mod;
		x=x*x%mod;
		k/=2;
	}
	return sss;
}
ll ny(ll x){return Power(x,mod-2);}
ll C(int x,int y)
{
	if (y>x || y<0) return 0;
	if (y==x || y==0) return 1;
	ll sss=jc[x];
	sss=sss *jc_ny[x-y]%mod *jc_ny[y]%mod;
	return sss;
}
void init()
{
	jc[0]=1; jc_ny[0]=1;
	for (int i=1;i<=n;++i) jc[i]=jc[i-1]*i%mod,jc_ny[i]=ny(jc[i]);
}
void dfs(int x,int fa)
{
	deep[x]=deep[fa]+1;
	size[x]=1;
	int len=son[x].size();
	for (int i=0;i<len;++i)
	{
		int y=son[x][i];
		if (y==fa) continue;
		dfs(y,x);
		size[x]+=size[y];
	}
}
void get_dis(int x,int fa)
{
	int len=son[x].size();
	for (int i=0;i<len;++i)
	{
		int y=son[x][i];
		if (y==fa) continue;
		dis[y]=dis[x] -size[y] +(n-size[y]);
		get_dis(y,x);
	}
}
int main()
{
//	freopen("F.in","r",stdin);
//	freopen("F.out","w",stdout);

	scanf("%d",&n);
	init();
//	printf("%lld %lld\n",jc[3],jc_ny[3]);
//	printf("%lld\n",C(5,3));
	int x,y;
	for (int i=1;i<n;++i) 
	{
		scanf("%d%d",&x,&y);
		son[x].push_back(y);
		son[y].push_back(x);
	}
	deep[0]=-1;
	dfs(1,0);
	for (int i=1;i<=n;++i) dis[1]+=deep[i];
	get_dis(1,0);
//	for (int i=1;i<=n;++i) printf("%d ",size[i]);
//	printf("\n");
//	for (int i=1;i<=n;++i) printf("%lld ",dis[i]);
//	printf("\n");
	minn=inf;
	for (int i=1;i<=n;++i) minn=min(minn,dis[i]);
	for (int i=1;i<=n;++i) if (dis[i]==minn)
	{
		if (!root) root=i;
		else
		{
			printf("%lld\n",jc[n/2]*jc[n/2]%mod);
			return 0;
		}
	}
//	printf("root:%d\n",root);

	dfs(root,0);
	f[0][0]=1;
	int len=son[root].size(),sum=0;
	for (int i=1;i<=len;++i)
	{
		int y=son[root][i-1];
//		printf("%d : %d\n",y,size[y]);
		for (int j=0;j<=sum;++j) for (int k=0;k<=size[y];++k)
			(f[i][j+k]+= f[i-1][j]*C(size[y],k) %mod *C(size[y],k) %mod *jc[k]%mod )%=mod;
		
		sum+=size[y];
	}
	for (int i=0;i<=n;++i)
	{
		ll sss=f[len][i]*jc[n-i]%mod;
		if (i%2==0) ans+=sss;
		else ans-=sss;
	}
	printf("%lld\n",(ans%mod +mod)%mod);
	return 0;
}
```