/*ID:PROG:LANG:*/
#include<bits/stdc++.h>
#define LL long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define MAXN 5005
using namespace std;
struct Edge{
	int to,nex;Edge(int _=0,int __=0){to=_,nex=__;}
}e[MAXN<<1];
int n,ans,cnt,rt,S,hd[MAXN],sz[MAXN],dp[2][MAXN];
LL jc[MAXN],njc[MAXN];
int rd(){
	int x=0,tp=1;char c=getchar();
	while(c<'0' || c>'9'){if(c=='-')tp=-1;c=getchar();}
	while(c>='0' && c<='9'){x=(x*10+c-'0');c=getchar();}
	return x*tp;
}
void adde(int x,int y){e[++cnt]=Edge(y,hd[x]);hd[x]=cnt;}
LL quick_mod(LL a,LL x){LL res=1;while(x){if(x&1)(res*=a)%=MOD;(a*=a)%=MOD,x>>=1;}return res;}
LL C(int n,int m){if(n<m)return 0;return jc[n]*njc[m]%MOD*njc[n-m]%MOD;}
LL C2(int n,int m){LL t=C(n,m);return t*t%MOD;}
void dfs(int now,int fa){
	sz[now]=1;int mx=0;
	for(int i=hd[now];i;i=e[i].nex)
		if(e[i].to!=fa)
			dfs(e[i].to,now),sz[now]+=sz[e[i].to],mx=max(mx,sz[e[i].to]);
	mx=max(mx,n-sz[now]);
	if(mx*2<=n)rt=now;
}
int main(){
	// freopen("testdata.in","r",stdin);
	// freopen("1.out","w",stdout);
	int x,y;
	n=rd();
	jc[0]=njc[0]=1;
	for(int i=1;i<=n;i++)jc[i]=jc[i-1]*i%MOD;
	njc[n]=quick_mod(jc[n],MOD-2);
	for(int i=n-1;i;i--)njc[i]=njc[i+1]*(i+1)%MOD;
	for(int i=1;i<n;i++){
		x=rd(),y=rd();
		adde(x,y),adde(y,x);
	}
	dfs(1,0),dfs(rt,0);
	dp[0][0]=1;
	bool now=1,las=0;
	for(int i=hd[rt];i;i=e[i].nex){
		for(int j=0;j<=S;j++)
			if(dp[las][j])
				for(int k=0;k<=sz[e[i].to];k++)
					(dp[now][j+k]+=1ll*dp[las][j]*C2(sz[e[i].to],k)%MOD*jc[k]%MOD)%=MOD;
		S+=sz[e[i].to];
		memset(dp[las],0,sizeof(dp[las]));
		now^=1,las^=1;
	}
	for(int i=0;i<=n;i++){
		if(i&1)(ans-=dp[las][i]*jc[n-i]%MOD)%=MOD;
		else (ans+=dp[las][i]*jc[n-i]%MOD)%=MOD;
	}
	printf("%d\n",(ans+MOD)%MOD);
	// printf("%.2lf\n",(double)clock()/CLOCKS_PER_SEC);
	return 0;
}
### 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
/*ID:PROG:LANG:*/
#include<bits/stdc++.h>
#define LL long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define MAXN 5005
using namespace std;
struct Edge{
	int to,nex;Edge(int _=0,int __=0){to=_,nex=__;}
}e[MAXN<<1];
int n,ans,cnt,rt,S,hd[MAXN],sz[MAXN],dp[2][MAXN];
LL jc[MAXN],njc[MAXN];
int rd(){
	int x=0,tp=1;char c=getchar();
	while(c<'0' || c>'9'){if(c=='-')tp=-1;c=getchar();}
	while(c>='0' && c<='9'){x=(x*10+c-'0');c=getchar();}
	return x*tp;
}
void adde(int x,int y){e[++cnt]=Edge(y,hd[x]);hd[x]=cnt;}
LL quick_mod(LL a,LL x){LL res=1;while(x){if(x&1)(res*=a)%=MOD;(a*=a)%=MOD,x>>=1;}return res;}
LL C(int n,int m){if(n<m)return 0;return jc[n]*njc[m]%MOD*njc[n-m]%MOD;}
LL C2(int n,int m){LL t=C(n,m);return t*t%MOD;}
void dfs(int now,int fa){
	sz[now]=1;int mx=0;
	for(int i=hd[now];i;i=e[i].nex)
		if(e[i].to!=fa)
			dfs(e[i].to,now),sz[now]+=sz[e[i].to],mx=max(mx,sz[e[i].to]);
	mx=max(mx,n-sz[now]);
	if(mx*2<=n)rt=now;
}
int main(){
	// freopen("testdata.in","r",stdin);
	// freopen("1.out","w",stdout);
	int x,y;
	n=rd();
	jc[0]=njc[0]=1;
	for(int i=1;i<=n;i++)jc[i]=jc[i-1]*i%MOD;
	njc[n]=quick_mod(jc[n],MOD-2);
	for(int i=n-1;i;i--)njc[i]=njc[i+1]*(i+1)%MOD;
	for(int i=1;i<n;i++){
		x=rd(),y=rd();
		adde(x,y),adde(y,x);
	}
	dfs(1,0),dfs(rt,0);
	dp[0][0]=1;
	bool now=1,las=0;
	for(int i=hd[rt];i;i=e[i].nex){
		for(int j=0;j<=S;j++)
			if(dp[las][j])
				for(int k=0;k<=sz[e[i].to];k++)
					(dp[now][j+k]+=1ll*dp[las][j]*C2(sz[e[i].to],k)%MOD*jc[k]%MOD)%=MOD;
		S+=sz[e[i].to];
		memset(dp[las],0,sizeof(dp[las]));
		now^=1,las^=1;
	}
	for(int i=0;i<=n;i++){
		if(i&1)(ans-=dp[las][i]*jc[n-i]%MOD)%=MOD;
		else (ans+=dp[las][i]*jc[n-i]%MOD)%=MOD;
	}
	printf("%d\n",(ans+MOD)%MOD);
	// printf("%.2lf\n",(double)clock()/CLOCKS_PER_SEC);
	return 0;
}
```