#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long
using namespace std;

int n,cnt=0,root,now=0x3f3f3f3f,cot,son=0,head[5010],sz[5010];
ll ans=0,fac[5010],inv[5010],f[2][5010];
struct edge{
	int u,v,nxt;
}e[100010];

void add(int u,int v){
	e[++cnt]=(edge){u,v,head[u]};
	head[u]=cnt;
}

ll fpow(ll x,ll y){
	ll ret=1;
	while(y){
		if(y&1)ret=ret*x%mod;
		x=x*x%mod;y>>=1;
	}
	return ret;
}
ll C(ll x,ll y){
	return fac[x]*inv[x-y]%mod*inv[y]%mod;
}

void dfs(int u,int fa){
	sz[u]=1;int mx=0;
	for(int i=head[u];i;i=e[i].nxt)
	  if(e[i].v!=fa){
	  	dfs(e[i].v,u);
	  	sz[u]+=sz[e[i].v];
	  	mx=max(mx,sz[e[i].v]);
	  }
	mx=max(mx,n-sz[u]);
	if(now==mx)cot++;
	if(now>mx)now=mx,root=u,cot=0;
}

int main()
{
	scanf("%d",&n);
	f[0][0]=fac[0]=fac[1]=inv[0]=inv[1]=1;
	for(int i=2;i<=n;i++)fac[i]=fac[i-1]*i%mod,inv[i]=fpow(fac[i],mod-2);
	for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),add(u,v),add(v,u);
	dfs(1,0);cot=0;dfs(root,0);
	if(cot>1)return printf("%lld",fac[n/2]*fac[n/2]%mod),0;
	int tot=0;
	for(int i=head[root];i;i=e[i].nxt){
		int v=e[i].v;son++;tot+=sz[v];
		memset(f[son&1],0,sizeof(f[son&1]));
		for(int j=tot;j>=0;j--)
		  for(int k=0;k<=min(j,sz[v]);k++)
		    f[son&1][j]=(f[son&1][j]+f[(son&1)^1][j-k]*C(sz[v],k)%mod*fac[sz[v]]%mod*inv[sz[v]-k])%mod;
	}
	for(int i=0,t=1;i<n;i++,t=-t)ans=(ans+1ll*t*f[son&1][i]*fac[n-i])%mod;
	printf("%lld",(ans+mod)%mod);
	return 0;
}
### Prompt

In cpp, your task is to solve 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 mod 1000000007
#define ll long long
using namespace std;

int n,cnt=0,root,now=0x3f3f3f3f,cot,son=0,head[5010],sz[5010];
ll ans=0,fac[5010],inv[5010],f[2][5010];
struct edge{
	int u,v,nxt;
}e[100010];

void add(int u,int v){
	e[++cnt]=(edge){u,v,head[u]};
	head[u]=cnt;
}

ll fpow(ll x,ll y){
	ll ret=1;
	while(y){
		if(y&1)ret=ret*x%mod;
		x=x*x%mod;y>>=1;
	}
	return ret;
}
ll C(ll x,ll y){
	return fac[x]*inv[x-y]%mod*inv[y]%mod;
}

void dfs(int u,int fa){
	sz[u]=1;int mx=0;
	for(int i=head[u];i;i=e[i].nxt)
	  if(e[i].v!=fa){
	  	dfs(e[i].v,u);
	  	sz[u]+=sz[e[i].v];
	  	mx=max(mx,sz[e[i].v]);
	  }
	mx=max(mx,n-sz[u]);
	if(now==mx)cot++;
	if(now>mx)now=mx,root=u,cot=0;
}

int main()
{
	scanf("%d",&n);
	f[0][0]=fac[0]=fac[1]=inv[0]=inv[1]=1;
	for(int i=2;i<=n;i++)fac[i]=fac[i-1]*i%mod,inv[i]=fpow(fac[i],mod-2);
	for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),add(u,v),add(v,u);
	dfs(1,0);cot=0;dfs(root,0);
	if(cot>1)return printf("%lld",fac[n/2]*fac[n/2]%mod),0;
	int tot=0;
	for(int i=head[root];i;i=e[i].nxt){
		int v=e[i].v;son++;tot+=sz[v];
		memset(f[son&1],0,sizeof(f[son&1]));
		for(int j=tot;j>=0;j--)
		  for(int k=0;k<=min(j,sz[v]);k++)
		    f[son&1][j]=(f[son&1][j]+f[(son&1)^1][j-k]*C(sz[v],k)%mod*fac[sz[v]]%mod*inv[sz[v]-k])%mod;
	}
	for(int i=0,t=1;i<n;i++,t=-t)ans=(ans+1ll*t*f[son&1][i]*fac[n-i])%mod;
	printf("%lld",(ans+mod)%mod);
	return 0;
}
```