#include<bits/stdc++.h>
typedef long long ll;
#define mod 1000000007
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
std::mt19937 rnd(time(NULL));
#define rand rnd
#define pr std::pair<int,int>
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
template<class T>void cxk(T&a,T b){a=a>b?a:b;}
template<class T>void cnk(T&a,T b){a=a<b?a:b;}
#ifdef mod
int pow(int x,int y){
	int ret=1;
	while(y){
		if(y&1)ret=1ll*ret*x%mod;
		x=1ll*x*x%mod;y>>=1;
	}
	return ret;
}
template<class Ta,class Tb>void inc(Ta&a,Tb b){a=a+b>=mod?a+b-mod:a+b;}
template<class Ta,class Tb>void dec(Ta&a,Tb b){a=a>=b?a-b:a+mod-b;}
#endif
int n,fir[5010],dis[100010],nxt[10010],id,fact[5010],ifact[5010],ans=0,siz[5010],rt,f[5010];
void link(int a,int b){nxt[++id]=fir[a],fir[a]=id,dis[id]=b;}
void getrt(int x,int fa=-1){
	f[x]=0,siz[x]=1;
	for(int i=fir[x];i;i=nxt[i]){
		if(dis[i]==fa)continue;
		getrt(dis[i],x);
		siz[x]+=siz[dis[i]];
		cxk(f[x],siz[dis[i]]);
	}
	cxk(f[x],n-siz[x]);
	if(f[x]<f[rt])rt=x;
}
int C(int n,int m){return 1ll*fact[n]*ifact[m]%mod*ifact[n-m]%mod;}
int A(int n,int m){return 1ll*fact[n]*ifact[n-m]%mod;}
int F[5010];
int main(){
#ifdef LOCAL
	freopen("in.in","r",stdin);
	//freopen("out.out","w",stdout);
#endif
	n=gi();int a,b;
	for(int i=1;i<n;++i)a=gi(),b=gi(),link(a,b),link(b,a);
	fact[0]=1;for(int i=1;i<=n;++i)fact[i]=1ll*i*fact[i-1]%mod;
	ifact[n]=pow(fact[n],mod-2);for(int i=n;i;--i)ifact[i-1]=1ll*ifact[i]*i%mod;
	f[0]=1e9,getrt(1);getrt(rt);
	if(f[rt]*2==n)printf("%d\n",1ll*fact[n/2]*fact[n/2]%mod),exit(0);
	F[0]=1;
	for(int i=fir[rt];i;i=nxt[i]){
		int sz=siz[dis[i]];
		for(int j=n;~j;--j)
			for(int k=1;k<=j&&k<=sz;++k)
				inc(F[j],1ll*F[j-k]*C(sz,k)%mod*A(sz,k)%mod);
	}
	for(int i=0,w;i<=n;++i){
		w=1ll*F[i]*fact[n-i]%mod;if(i&1)w=mod-w;
		inc(ans,w);
	}
	printf("%d\n",ans);
	return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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>
typedef long long ll;
#define mod 1000000007
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
std::mt19937 rnd(time(NULL));
#define rand rnd
#define pr std::pair<int,int>
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
template<class T>void cxk(T&a,T b){a=a>b?a:b;}
template<class T>void cnk(T&a,T b){a=a<b?a:b;}
#ifdef mod
int pow(int x,int y){
	int ret=1;
	while(y){
		if(y&1)ret=1ll*ret*x%mod;
		x=1ll*x*x%mod;y>>=1;
	}
	return ret;
}
template<class Ta,class Tb>void inc(Ta&a,Tb b){a=a+b>=mod?a+b-mod:a+b;}
template<class Ta,class Tb>void dec(Ta&a,Tb b){a=a>=b?a-b:a+mod-b;}
#endif
int n,fir[5010],dis[100010],nxt[10010],id,fact[5010],ifact[5010],ans=0,siz[5010],rt,f[5010];
void link(int a,int b){nxt[++id]=fir[a],fir[a]=id,dis[id]=b;}
void getrt(int x,int fa=-1){
	f[x]=0,siz[x]=1;
	for(int i=fir[x];i;i=nxt[i]){
		if(dis[i]==fa)continue;
		getrt(dis[i],x);
		siz[x]+=siz[dis[i]];
		cxk(f[x],siz[dis[i]]);
	}
	cxk(f[x],n-siz[x]);
	if(f[x]<f[rt])rt=x;
}
int C(int n,int m){return 1ll*fact[n]*ifact[m]%mod*ifact[n-m]%mod;}
int A(int n,int m){return 1ll*fact[n]*ifact[n-m]%mod;}
int F[5010];
int main(){
#ifdef LOCAL
	freopen("in.in","r",stdin);
	//freopen("out.out","w",stdout);
#endif
	n=gi();int a,b;
	for(int i=1;i<n;++i)a=gi(),b=gi(),link(a,b),link(b,a);
	fact[0]=1;for(int i=1;i<=n;++i)fact[i]=1ll*i*fact[i-1]%mod;
	ifact[n]=pow(fact[n],mod-2);for(int i=n;i;--i)ifact[i-1]=1ll*ifact[i]*i%mod;
	f[0]=1e9,getrt(1);getrt(rt);
	if(f[rt]*2==n)printf("%d\n",1ll*fact[n/2]*fact[n/2]%mod),exit(0);
	F[0]=1;
	for(int i=fir[rt];i;i=nxt[i]){
		int sz=siz[dis[i]];
		for(int j=n;~j;--j)
			for(int k=1;k<=j&&k<=sz;++k)
				inc(F[j],1ll*F[j-k]*C(sz,k)%mod*A(sz,k)%mod);
	}
	for(int i=0,w;i<=n;++i){
		w=1ll*F[i]*fact[n-i]%mod;if(i&1)w=mod-w;
		inc(ans,w);
	}
	printf("%d\n",ans);
	return 0;
}

```