#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll ha,ans,n,m,tot,e[10000],nt[10010],hd[10010],c[5010][5010],sz[10010],a[10010],p=1e9+7,f[10010],jc[10010],ny[10010];
void build(ll x,ll y){
	tot++;
	e[tot]=y;
	nt[tot]=hd[x];hd[x]=tot;
}
void dfs(ll x,ll fa){
	ll i,mx=0;
	sz[x]=1;
	for(i=hd[x];i;i=nt[i]){
		if(e[i]==fa)continue;
		dfs(e[i],x);
		mx=max(mx,sz[e[i]]);
		sz[x]+=sz[e[i]];
	}
	mx=max(mx,n-sz[x]);
	if(mx<=n/2){
		ha++;
		for(i=hd[x];i;i=nt[i]){
			if(e[i]==fa)continue;
			a[++m]=sz[e[i]];
		}
		a[++m]=n-sz[x];
	}
}
ll ksm(ll x,ll y){
	ll xlh=1;
	while(y){
		if(y&1)xlh=xlh*x%p;
		x=x*x%p;
		y/=2;
	}
	return xlh;
}
int main(){
	ll now,i,x,y,j,sum=0,k;
	scanf("%lld",&n);
	for(i=1;i<n;i++){
		scanf("%lld%lld",&x,&y);
		build(x,y);build(y,x);
	}
	dfs(1,0);
	if(ha>1){
		ans=1;
		for(i=1;i<=n/2;i++)ans=ans*i%p;
		ans=ans*ans%p;
		printf("%lld",ans);
		return 0;
	}
	jc[0]=ny[0]=1;
	for(i=1;i<=n;i++)jc[i]=jc[i-1]*i%p,ny[i]=ksm(jc[i],p-2)%p;
	for(i=0;i<=n;i++)c[i][0]=1;
	for(i=1;i<=n;i++)
	 for(j=1;j<=i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;
	f[0]=1;
	for(i=1;i<=m;i++){
		//printf("%lld %lld\n",i,a[i]);
		sum+=a[i];
		for(j=sum;j>=0;j--){
			now=0;
		 for(k=0;k<=min(j,a[i]);k++)now=(now+f[j-k]*c[a[i]][k]%p*jc[a[i]]%p*ny[a[i]-k]%p)%p;
		 f[j]=now;
	  }
	}
	for(i=0;i<n;i++){
		//printf("%lld %lld\n",i,f[i]);
		sum=f[i]*jc[n-i]%p;
		if(i%2==0)ans=(ans+sum)%p;
		 else ans=(ans-sum+p)%p;
	}
	printf("%lld",ans);
}
/*
不（很）难想到所有点经过重心就是最优解 
*/
### Prompt

Generate 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;
ll ha,ans,n,m,tot,e[10000],nt[10010],hd[10010],c[5010][5010],sz[10010],a[10010],p=1e9+7,f[10010],jc[10010],ny[10010];
void build(ll x,ll y){
	tot++;
	e[tot]=y;
	nt[tot]=hd[x];hd[x]=tot;
}
void dfs(ll x,ll fa){
	ll i,mx=0;
	sz[x]=1;
	for(i=hd[x];i;i=nt[i]){
		if(e[i]==fa)continue;
		dfs(e[i],x);
		mx=max(mx,sz[e[i]]);
		sz[x]+=sz[e[i]];
	}
	mx=max(mx,n-sz[x]);
	if(mx<=n/2){
		ha++;
		for(i=hd[x];i;i=nt[i]){
			if(e[i]==fa)continue;
			a[++m]=sz[e[i]];
		}
		a[++m]=n-sz[x];
	}
}
ll ksm(ll x,ll y){
	ll xlh=1;
	while(y){
		if(y&1)xlh=xlh*x%p;
		x=x*x%p;
		y/=2;
	}
	return xlh;
}
int main(){
	ll now,i,x,y,j,sum=0,k;
	scanf("%lld",&n);
	for(i=1;i<n;i++){
		scanf("%lld%lld",&x,&y);
		build(x,y);build(y,x);
	}
	dfs(1,0);
	if(ha>1){
		ans=1;
		for(i=1;i<=n/2;i++)ans=ans*i%p;
		ans=ans*ans%p;
		printf("%lld",ans);
		return 0;
	}
	jc[0]=ny[0]=1;
	for(i=1;i<=n;i++)jc[i]=jc[i-1]*i%p,ny[i]=ksm(jc[i],p-2)%p;
	for(i=0;i<=n;i++)c[i][0]=1;
	for(i=1;i<=n;i++)
	 for(j=1;j<=i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;
	f[0]=1;
	for(i=1;i<=m;i++){
		//printf("%lld %lld\n",i,a[i]);
		sum+=a[i];
		for(j=sum;j>=0;j--){
			now=0;
		 for(k=0;k<=min(j,a[i]);k++)now=(now+f[j-k]*c[a[i]][k]%p*jc[a[i]]%p*ny[a[i]-k]%p)%p;
		 f[j]=now;
	  }
	}
	for(i=0;i<n;i++){
		//printf("%lld %lld\n",i,f[i]);
		sum=f[i]*jc[n-i]%p;
		if(i%2==0)ans=(ans+sum)%p;
		 else ans=(ans-sum+p)%p;
	}
	printf("%lld",ans);
}
/*
不（很）难想到所有点经过重心就是最优解 
*/
```