#include<bits/stdc++.h>
using namespace std; 
#define ll long long
#define rep(i,x,y)  for(ll i=x;i<y;++i)
#define For(i,x,y)  for(ll i=x;i<=y;++i) 
#define FOr(i,x,y)  for(ll i=x;i>=y;--i) 
#define pi acos(-1)
#define mk make_pair<ll,ll>
#define pa pair<ll,ll>
#define fi first
#define se second
#define lf else if
#define max(x,y)    ((x)<(y)?(y):(x))
#define min(x,y)    ((x)<(y)?(x):(y))
#define mul(x,y)	x=x*(y)%mod
#define Add(x,y)	x=(x+(y))%mod
#define EXIT(x)	return writeln(x),0;
typedef complex<double> E;
namespace SHENZHEBEI{
#ifdef LOCAL
	struct _{_(){freopen("cf.in","r",stdin);}}_;
#endif 
#define NEG 0
    const int L=2333333;
    char SZB[L],*S=SZB,*T=SZB;
    inline char gc(){   if (S==T){  T=(S=SZB)+fread(SZB,1,L,stdin); if (S==T) return '\n';  }   return *S++;    }
#if NEG
    inline ll read(){    ll x=0,f=1; char ch=gc();   for (;!isdigit(ch);ch=gc()) if (ch=='-') f=-1;  for (;isdigit(ch);ch=gc())  x=x*10-48+ch;   return x*f; }
    inline void write(ll x){    if (x<0) putchar('-'),x=-x;  if (x>=10)   write(x/10);    putchar(x%10+'0');  }
#else
    inline ll read(){    ll x=0; char ch=gc();   for (;!isdigit(ch);ch=gc());    for (;isdigit(ch);ch=gc())  x=x*10-48+ch;   return x;   }
    inline void write(ll x){    if (x>=10)   write(x/10);    putchar(x%10+'0');  }
#endif
    inline char readchar(){ char ch=gc();   for(;isspace(ch);ch=gc());  return ch;  }
    inline ll readstr(char *s){ char ch=gc();   int cur=0;  for(;isspace(ch);ch=gc());      for(;!isspace(ch);ch=gc())  s[cur++]=ch;    s[cur]='\0';    return cur; }
    inline void writeln(ll x){  write(x);   puts("");   }
}using namespace SHENZHEBEI;
const ll N=10010,mod=1e9+7;
ll g[N],h[N],head[N],nxt[N],vet[N],fac[N],n,tot,cnt,sz[N],son[N],inv[N],rt,SZ,f[N];
void insert(ll x,ll y){	nxt[++tot]=head[x];head[x]=tot;vet[tot]=y;}
void dfs(ll x,ll pre){
	sz[x]=1;
	for(ll i=head[x];i;i=nxt[i])if (vet[i]!=pre)
		dfs(vet[i],x),sz[x]+=sz[vet[i]],son[x]=max(son[x],sz[vet[i]]);
	son[x]=max(son[x],n-sz[x]);
	if (son[x]<=n/2)	rt=x,++cnt;
}
ll C(ll a,ll b){	return a<b?0:fac[a]*inv[b]%mod*inv[a-b]%mod;	}
int main(){
	n=read();
	fac[0]=inv[0]=fac[1]=inv[1]=1;
	For(i,2,n)inv[i]=inv[mod%i]*(mod-mod/i)%mod;
	For(i,2,n)inv[i]=inv[i-1]*inv[i]%mod,fac[i]=fac[i-1]*i%mod;
	For(i,2,n){
		ll x=read(),y=read();
		insert(x,y),insert(y,x);
	}dfs(1,0);
	if (cnt==2)	return writeln(fac[n/2]*fac[n/2]%mod),0;
	dfs(rt,0);
	f[0]=1;
	for(ll i=head[rt];i;i=nxt[i]){
		ll t=sz[vet[i]];
		For(j,0,t)	g[j]=C(t,j)*C(t,j)%mod*fac[j]%mod;
		memset(h,0,sizeof h);
		For(j,0,SZ)	For(k,0,t)	Add(h[j+k],f[j]*g[k]);
		memcpy(f,h,sizeof h);
		SZ+=t;
	}
//	For(i,0,n)writeln(f[i]);
	FOr(i,n,0){
		f[i]=f[i]*fac[n-i]%mod;
		For(j,i+1,n)	f[i]=(f[i]-f[j]*C(j,i))%mod;
	}
	writeln((f[0]%mod+mod)%mod);
}
/*
f[i][j]
i*(i-1)*(i-2)
*/
### 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<bits/stdc++.h>
using namespace std; 
#define ll long long
#define rep(i,x,y)  for(ll i=x;i<y;++i)
#define For(i,x,y)  for(ll i=x;i<=y;++i) 
#define FOr(i,x,y)  for(ll i=x;i>=y;--i) 
#define pi acos(-1)
#define mk make_pair<ll,ll>
#define pa pair<ll,ll>
#define fi first
#define se second
#define lf else if
#define max(x,y)    ((x)<(y)?(y):(x))
#define min(x,y)    ((x)<(y)?(x):(y))
#define mul(x,y)	x=x*(y)%mod
#define Add(x,y)	x=(x+(y))%mod
#define EXIT(x)	return writeln(x),0;
typedef complex<double> E;
namespace SHENZHEBEI{
#ifdef LOCAL
	struct _{_(){freopen("cf.in","r",stdin);}}_;
#endif 
#define NEG 0
    const int L=2333333;
    char SZB[L],*S=SZB,*T=SZB;
    inline char gc(){   if (S==T){  T=(S=SZB)+fread(SZB,1,L,stdin); if (S==T) return '\n';  }   return *S++;    }
#if NEG
    inline ll read(){    ll x=0,f=1; char ch=gc();   for (;!isdigit(ch);ch=gc()) if (ch=='-') f=-1;  for (;isdigit(ch);ch=gc())  x=x*10-48+ch;   return x*f; }
    inline void write(ll x){    if (x<0) putchar('-'),x=-x;  if (x>=10)   write(x/10);    putchar(x%10+'0');  }
#else
    inline ll read(){    ll x=0; char ch=gc();   for (;!isdigit(ch);ch=gc());    for (;isdigit(ch);ch=gc())  x=x*10-48+ch;   return x;   }
    inline void write(ll x){    if (x>=10)   write(x/10);    putchar(x%10+'0');  }
#endif
    inline char readchar(){ char ch=gc();   for(;isspace(ch);ch=gc());  return ch;  }
    inline ll readstr(char *s){ char ch=gc();   int cur=0;  for(;isspace(ch);ch=gc());      for(;!isspace(ch);ch=gc())  s[cur++]=ch;    s[cur]='\0';    return cur; }
    inline void writeln(ll x){  write(x);   puts("");   }
}using namespace SHENZHEBEI;
const ll N=10010,mod=1e9+7;
ll g[N],h[N],head[N],nxt[N],vet[N],fac[N],n,tot,cnt,sz[N],son[N],inv[N],rt,SZ,f[N];
void insert(ll x,ll y){	nxt[++tot]=head[x];head[x]=tot;vet[tot]=y;}
void dfs(ll x,ll pre){
	sz[x]=1;
	for(ll i=head[x];i;i=nxt[i])if (vet[i]!=pre)
		dfs(vet[i],x),sz[x]+=sz[vet[i]],son[x]=max(son[x],sz[vet[i]]);
	son[x]=max(son[x],n-sz[x]);
	if (son[x]<=n/2)	rt=x,++cnt;
}
ll C(ll a,ll b){	return a<b?0:fac[a]*inv[b]%mod*inv[a-b]%mod;	}
int main(){
	n=read();
	fac[0]=inv[0]=fac[1]=inv[1]=1;
	For(i,2,n)inv[i]=inv[mod%i]*(mod-mod/i)%mod;
	For(i,2,n)inv[i]=inv[i-1]*inv[i]%mod,fac[i]=fac[i-1]*i%mod;
	For(i,2,n){
		ll x=read(),y=read();
		insert(x,y),insert(y,x);
	}dfs(1,0);
	if (cnt==2)	return writeln(fac[n/2]*fac[n/2]%mod),0;
	dfs(rt,0);
	f[0]=1;
	for(ll i=head[rt];i;i=nxt[i]){
		ll t=sz[vet[i]];
		For(j,0,t)	g[j]=C(t,j)*C(t,j)%mod*fac[j]%mod;
		memset(h,0,sizeof h);
		For(j,0,SZ)	For(k,0,t)	Add(h[j+k],f[j]*g[k]);
		memcpy(f,h,sizeof h);
		SZ+=t;
	}
//	For(i,0,n)writeln(f[i]);
	FOr(i,n,0){
		f[i]=f[i]*fac[n-i]%mod;
		For(j,i+1,n)	f[i]=(f[i]-f[j]*C(j,i))%mod;
	}
	writeln((f[0]%mod+mod)%mod);
}
/*
f[i][j]
i*(i-1)*(i-2)
*/
```