#include<cstdio>
#include<cstring>
typedef long long LL;
const int N=5005,md=1e9+7;
int n,head[N],cnt,sz[N],mxd[N],rt,fac[N],iv[N],root;
int f[2][N];
bool tag;
struct edge{
	int to,nxt;
}e[N<<1];
inline int C(int n,int m){return(LL)fac[n]*iv[m]%md*iv[n-m]%md;}
inline int P(int n,int m){return(LL)fac[n]*iv[n-m]%md;}
inline int pow(int a,int b){
	int ret=1;
	for(;b;b>>=1,a=(LL)a*a%md)if(b&1)ret=(LL)ret*a%md;
	return ret;
}
void getrt(int now,int pre){
	sz[now]=1,mxd[now]=0;
	for(int i=head[now];i;i=e[i].nxt)
		if(e[i].to!=pre){
			getrt(e[i].to,now);
			sz[now]+=sz[e[i].to];
			if(mxd[now]<sz[e[i].to])mxd[now]=sz[e[i].to];
		}
	if(mxd[now]<n-sz[now])mxd[now]=n-sz[now];
	if(!rt||mxd[now]<mxd[rt])rt=now,tag=0;
	else if(mxd[now]==mxd[rt])tag=1;
}
int main(){
	scanf("%d",&n);
	for(int i=*fac=1;i<=n;++i)fac[i]=(LL)fac[i-1]*i%md;
	iv[n]=pow(fac[n],md-2);
	for(int i=n-1;~i;--i)iv[i]=(i+1LL)*iv[i+1]%md;
	for(int i=1;i<n;++i){
		int u,v;
		scanf("%d%d",&u,&v);
		e[++cnt]=(edge){v,head[u]},head[u]=cnt;
		e[++cnt]=(edge){u,head[v]},head[v]=cnt;
	}
	rt=0;
	getrt(1,0);
	if(tag){
		printf("%lld\n",(LL)fac[n/2]*fac[n/2]%md);
		return 0;
	}
	root=rt,rt=0;
	getrt(root,0);
	int cur=0,lim=0;
	f[0][0]=1;
	for(int i=head[rt];i;i=e[i].nxt){
		int to=e[i].to;
		cur^=1;
		memset(f[cur],0,sizeof*f);
		lim+=sz[to];
		for(int j=lim;~j;--j)
			for(int k=0;k<=j&&k<=sz[to];++k)
				f[cur][j]=(f[cur][j]+(LL)f[cur^1][j-k]*C(sz[to],k)%md*P(sz[to],k))%md;
	}
	int ans=0;
	for(int i=0,x=1;i<=n;++i,x=md-x)
		ans=(ans+(LL)x*f[cur][i]%md*fac[n-i])%md;
	printf("%d\n",ans);
	return 0;
}
### Prompt

Your challenge is to write 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<cstdio>
#include<cstring>
typedef long long LL;
const int N=5005,md=1e9+7;
int n,head[N],cnt,sz[N],mxd[N],rt,fac[N],iv[N],root;
int f[2][N];
bool tag;
struct edge{
	int to,nxt;
}e[N<<1];
inline int C(int n,int m){return(LL)fac[n]*iv[m]%md*iv[n-m]%md;}
inline int P(int n,int m){return(LL)fac[n]*iv[n-m]%md;}
inline int pow(int a,int b){
	int ret=1;
	for(;b;b>>=1,a=(LL)a*a%md)if(b&1)ret=(LL)ret*a%md;
	return ret;
}
void getrt(int now,int pre){
	sz[now]=1,mxd[now]=0;
	for(int i=head[now];i;i=e[i].nxt)
		if(e[i].to!=pre){
			getrt(e[i].to,now);
			sz[now]+=sz[e[i].to];
			if(mxd[now]<sz[e[i].to])mxd[now]=sz[e[i].to];
		}
	if(mxd[now]<n-sz[now])mxd[now]=n-sz[now];
	if(!rt||mxd[now]<mxd[rt])rt=now,tag=0;
	else if(mxd[now]==mxd[rt])tag=1;
}
int main(){
	scanf("%d",&n);
	for(int i=*fac=1;i<=n;++i)fac[i]=(LL)fac[i-1]*i%md;
	iv[n]=pow(fac[n],md-2);
	for(int i=n-1;~i;--i)iv[i]=(i+1LL)*iv[i+1]%md;
	for(int i=1;i<n;++i){
		int u,v;
		scanf("%d%d",&u,&v);
		e[++cnt]=(edge){v,head[u]},head[u]=cnt;
		e[++cnt]=(edge){u,head[v]},head[v]=cnt;
	}
	rt=0;
	getrt(1,0);
	if(tag){
		printf("%lld\n",(LL)fac[n/2]*fac[n/2]%md);
		return 0;
	}
	root=rt,rt=0;
	getrt(root,0);
	int cur=0,lim=0;
	f[0][0]=1;
	for(int i=head[rt];i;i=e[i].nxt){
		int to=e[i].to;
		cur^=1;
		memset(f[cur],0,sizeof*f);
		lim+=sz[to];
		for(int j=lim;~j;--j)
			for(int k=0;k<=j&&k<=sz[to];++k)
				f[cur][j]=(f[cur][j]+(LL)f[cur^1][j-k]*C(sz[to],k)%md*P(sz[to],k))%md;
	}
	int ans=0;
	for(int i=0,x=1;i<=n;++i,x=md-x)
		ans=(ans+(LL)x*f[cur][i]%md*fac[n-i])%md;
	printf("%d\n",ans);
	return 0;
}
```