#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
int n,m,cnt,inf=1e9,q[5010],tot;
ll ans,f[5010],g[5010],mo=1e9+7,jc[5010],ny[5010];
bool flag;
ll pw(ll i,ll k)
{
	ll a=1;
	while(k)
	{
		if(k&1)a*=i,a%=mo;
		i*=i;i%=mo;
		k>>=1;
	}
	return a;
}
ll cc(ll a,ll b)
{
	if(a<b)return 0;
	return jc[a]*ny[b]%mo*ny[a-b]%mo;
}
ll aa(ll a,ll b)
{
	if(a<b)return 0;
	return jc[a]*ny[a-b]%mo;
}
void add(ll &a,ll b)
{
	a+=b;
	if(a>=mo)a-=mo;
}
struct graph
{
	int x1[5010],r[10010],vt[10010],su[10010],mx,cen;
	void adde(int a,int b)
	{
		r[++cnt]=x1[a];x1[a]=cnt;vt[cnt]=b;
		r[++cnt]=x1[b];x1[b]=cnt;vt[cnt]=a;
	}
	void dfs(int i,int fa)
	{
		int s,a,b,j,k;
		a=x1[i];su[i]=1;
		k=0;
		while(a)
		{
			b=vt[a];
			if(b!=fa)
			{
				dfs(b,i);
				su[i]+=su[b];
				if(su[b]>k)k=su[b];
			}
			a=r[a];
		}
		if(n-su[i]>k)k=n-su[i];
		if(su[i]*2==n)flag=1;
		if(k<mx)mx=k,cen=i;
	}
	void solve()
	{
		int i,s,a,b,j,k;
		a=x1[cen];
		while(a)
		{
			b=vt[a];
			if(su[b]<su[cen])q[++tot]=su[b];
			a=r[a];
		}
		if(cen!=1)q[++tot]=n-su[cen];
		//cout<<"tot "<<tot<<endl;
		//for(i=1;i<=tot;i++)cout<<" "<<q[i];cout<<endl;
		f[0]=1;ans=jc[n];
		for(i=1;i<=tot;i++)
		{	
			for(s=0;s<=n;s++)
				for(k=1;k<=q[i];k++)
					if(s+k<=n)add(g[s+k],f[s]*cc(q[i],k)%mo*aa(q[i],k)%mo);
			for(s=0;s<=n;s++)add(f[s],g[s]),g[s]=0;	
		}
		for(i=1;i<=n;i++)
		{
			//cout<<"f "<<i<<" "<<f[i]<<endl;
			if(i&1)add(ans,mo-(f[i]*jc[n-i]%mo));
			else add(ans,f[i]*jc[n-i]%mo);
		}
		printf("%lld",ans);
	}
}gr;
int main()
{
	int i,s,a,b,j,k;
	jc[0]=ny[0]=1;for(i=1;i<=5000;i++)jc[i]=jc[i-1]*i%mo,ny[i]=pw(jc[i],mo-2);
	scanf("%d",&n);
	for(i=1;i<n;i++)scanf("%d%d",&a,&b),gr.adde(a,b);
	gr.mx=inf;gr.cen=0;gr.dfs(1,0);
	if(flag){printf("%lld",jc[n/2]*jc[n/2]%mo);return 0;}
	//cout<<"sb "<<gr.cen<<endl;
	gr.solve();
	return 0;
}
### Prompt

Please formulate 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<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
int n,m,cnt,inf=1e9,q[5010],tot;
ll ans,f[5010],g[5010],mo=1e9+7,jc[5010],ny[5010];
bool flag;
ll pw(ll i,ll k)
{
	ll a=1;
	while(k)
	{
		if(k&1)a*=i,a%=mo;
		i*=i;i%=mo;
		k>>=1;
	}
	return a;
}
ll cc(ll a,ll b)
{
	if(a<b)return 0;
	return jc[a]*ny[b]%mo*ny[a-b]%mo;
}
ll aa(ll a,ll b)
{
	if(a<b)return 0;
	return jc[a]*ny[a-b]%mo;
}
void add(ll &a,ll b)
{
	a+=b;
	if(a>=mo)a-=mo;
}
struct graph
{
	int x1[5010],r[10010],vt[10010],su[10010],mx,cen;
	void adde(int a,int b)
	{
		r[++cnt]=x1[a];x1[a]=cnt;vt[cnt]=b;
		r[++cnt]=x1[b];x1[b]=cnt;vt[cnt]=a;
	}
	void dfs(int i,int fa)
	{
		int s,a,b,j,k;
		a=x1[i];su[i]=1;
		k=0;
		while(a)
		{
			b=vt[a];
			if(b!=fa)
			{
				dfs(b,i);
				su[i]+=su[b];
				if(su[b]>k)k=su[b];
			}
			a=r[a];
		}
		if(n-su[i]>k)k=n-su[i];
		if(su[i]*2==n)flag=1;
		if(k<mx)mx=k,cen=i;
	}
	void solve()
	{
		int i,s,a,b,j,k;
		a=x1[cen];
		while(a)
		{
			b=vt[a];
			if(su[b]<su[cen])q[++tot]=su[b];
			a=r[a];
		}
		if(cen!=1)q[++tot]=n-su[cen];
		//cout<<"tot "<<tot<<endl;
		//for(i=1;i<=tot;i++)cout<<" "<<q[i];cout<<endl;
		f[0]=1;ans=jc[n];
		for(i=1;i<=tot;i++)
		{	
			for(s=0;s<=n;s++)
				for(k=1;k<=q[i];k++)
					if(s+k<=n)add(g[s+k],f[s]*cc(q[i],k)%mo*aa(q[i],k)%mo);
			for(s=0;s<=n;s++)add(f[s],g[s]),g[s]=0;	
		}
		for(i=1;i<=n;i++)
		{
			//cout<<"f "<<i<<" "<<f[i]<<endl;
			if(i&1)add(ans,mo-(f[i]*jc[n-i]%mo));
			else add(ans,f[i]*jc[n-i]%mo);
		}
		printf("%lld",ans);
	}
}gr;
int main()
{
	int i,s,a,b,j,k;
	jc[0]=ny[0]=1;for(i=1;i<=5000;i++)jc[i]=jc[i-1]*i%mo,ny[i]=pw(jc[i],mo-2);
	scanf("%d",&n);
	for(i=1;i<n;i++)scanf("%d%d",&a,&b),gr.adde(a,b);
	gr.mx=inf;gr.cen=0;gr.dfs(1,0);
	if(flag){printf("%lld",jc[n/2]*jc[n/2]%mo);return 0;}
	//cout<<"sb "<<gr.cen<<endl;
	gr.solve();
	return 0;
}
```