#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define si scanf
#define so printf
#define N 5100
#define M 
#define INF  
#define mod %P
#define nxt t[j]
template<typename TP>inline bool rd(TP& r)
{
	r=0;
	char tmp=getchar();
	while(tmp<'0'||tmp>'9')
	{
		if(tmp==EOF)
			return 0;
		tmp=getchar();
	}
	while('0'<=tmp&&tmp<='9')
	{
		r=(r<<3)+(r<<1)+tmp-'0';
		tmp=getchar();
	}
	return 1;
	
} 
long long P=1000000007;
int n;
long long ans; 
long long prdc[N];
bool vis[N][N];
long long c[N][N]; 
void pre()
{
	prdc[0]=1;
	for(int i=1;i<=n;++i)
		prdc[i]=prdc[i-1]*i mod;	
}
long long C(int fr,int chos)
{
	if(fr<0||chos<0||fr<chos)
		return 0;
	if(chos==0||chos==fr)
		return 1;
	if(!vis[fr][chos])
	{
		c[fr][chos]=(C(fr-1,chos-1)+C(fr-1,chos))mod;
		vis[fr][chos]=1;
	}
	return c[fr][chos];
}
int h[N],x[N*2],t[N*2],tot=1;
void add(int u,int v)
{
	++tot;
	x[tot]=h[u];
	h[u]=tot;
	t[tot]=v;
}
int rt;
int sz[N],mxson[N];
void getroot(int now,int fa)
{
	for(int j=h[now];j;j=x[j])
		if(nxt!=fa)
		{
			getroot(nxt,now);
			sz[now]+=sz[nxt];
			mxson[now]=max(mxson[now],sz[nxt]);
		}
	if(rt==-1)
		return;
	++sz[now];
	if(n-sz[now]==sz[now])
		rt=-1;
	mxson[now]=max(mxson[now],n-sz[now]);
	if(mxson[now]<mxson[rt])
		rt=now;
}
void getsize(int now,int fa)
{
	sz[now]=0;
	for(int j=h[now];j;j=x[j])
		if(nxt!=fa)
		{
			getsize(nxt,now);
			sz[now]+=sz[nxt];
		}
	++sz[now];
}
long long g[2][N];
int main()
{
	rd(n);
	pre();
	int u,v;
	for(int i=1;i<n;++i)
	{
		rd(u),rd(v);
		add(u,v);
		add(v,u);
	}
	mxson[0]=n+100;
	getroot(1,0);
	if(rt==-1)
	{
		ans=prdc[n/2]*prdc[n/2]mod;
		so("%lld\n",ans);
		return 0;
	}
	int now=0;
	g[now][0]=1;
	for(int j=h[rt];j;j=x[j])
	{
		now^=1;
		getsize(nxt,rt);
		memset(g[now],0,sizeof(g[now]));
		for(int i=0;i<n;++i)
		{
			for(int k=0;k<=min(i,sz[nxt]);++k)
				g[now][i]=(g[now][i]+g[now^1][i-k]*C(sz[nxt],k)mod *C(sz[nxt],k)mod *prdc[k]mod)mod;
		}
	}
	for(int k=0;k<n;++k) 
		if(k&1)
			ans=(ans-g[now][k]*prdc[n-k]mod+P)mod;
		else
			ans=(ans+g[now][k]*prdc[n-k]mod)mod;
	so("%lld\n",ans);
	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<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define si scanf
#define so printf
#define N 5100
#define M 
#define INF  
#define mod %P
#define nxt t[j]
template<typename TP>inline bool rd(TP& r)
{
	r=0;
	char tmp=getchar();
	while(tmp<'0'||tmp>'9')
	{
		if(tmp==EOF)
			return 0;
		tmp=getchar();
	}
	while('0'<=tmp&&tmp<='9')
	{
		r=(r<<3)+(r<<1)+tmp-'0';
		tmp=getchar();
	}
	return 1;
	
} 
long long P=1000000007;
int n;
long long ans; 
long long prdc[N];
bool vis[N][N];
long long c[N][N]; 
void pre()
{
	prdc[0]=1;
	for(int i=1;i<=n;++i)
		prdc[i]=prdc[i-1]*i mod;	
}
long long C(int fr,int chos)
{
	if(fr<0||chos<0||fr<chos)
		return 0;
	if(chos==0||chos==fr)
		return 1;
	if(!vis[fr][chos])
	{
		c[fr][chos]=(C(fr-1,chos-1)+C(fr-1,chos))mod;
		vis[fr][chos]=1;
	}
	return c[fr][chos];
}
int h[N],x[N*2],t[N*2],tot=1;
void add(int u,int v)
{
	++tot;
	x[tot]=h[u];
	h[u]=tot;
	t[tot]=v;
}
int rt;
int sz[N],mxson[N];
void getroot(int now,int fa)
{
	for(int j=h[now];j;j=x[j])
		if(nxt!=fa)
		{
			getroot(nxt,now);
			sz[now]+=sz[nxt];
			mxson[now]=max(mxson[now],sz[nxt]);
		}
	if(rt==-1)
		return;
	++sz[now];
	if(n-sz[now]==sz[now])
		rt=-1;
	mxson[now]=max(mxson[now],n-sz[now]);
	if(mxson[now]<mxson[rt])
		rt=now;
}
void getsize(int now,int fa)
{
	sz[now]=0;
	for(int j=h[now];j;j=x[j])
		if(nxt!=fa)
		{
			getsize(nxt,now);
			sz[now]+=sz[nxt];
		}
	++sz[now];
}
long long g[2][N];
int main()
{
	rd(n);
	pre();
	int u,v;
	for(int i=1;i<n;++i)
	{
		rd(u),rd(v);
		add(u,v);
		add(v,u);
	}
	mxson[0]=n+100;
	getroot(1,0);
	if(rt==-1)
	{
		ans=prdc[n/2]*prdc[n/2]mod;
		so("%lld\n",ans);
		return 0;
	}
	int now=0;
	g[now][0]=1;
	for(int j=h[rt];j;j=x[j])
	{
		now^=1;
		getsize(nxt,rt);
		memset(g[now],0,sizeof(g[now]));
		for(int i=0;i<n;++i)
		{
			for(int k=0;k<=min(i,sz[nxt]);++k)
				g[now][i]=(g[now][i]+g[now^1][i-k]*C(sz[nxt],k)mod *C(sz[nxt],k)mod *prdc[k]mod)mod;
		}
	}
	for(int k=0;k<n;++k) 
		if(k&1)
			ans=(ans-g[now][k]*prdc[n-k]mod+P)mod;
		else
			ans=(ans+g[now][k]*prdc[n-k]mod)mod;
	so("%lld\n",ans);
	return 0;
} 
```