#include<bits/stdc++.h>
#define N 5005
#define pb push_back
using namespace std;
const int P=1e9+7;
bool __S;
int size[N],son[N],Q[N],father[N];
int b[N],sum[N],C[N][N],F[N][N],fac[N],n,m,root;
int Go[N<<1],Next[N<<1],Value[N<<1],End[N],cnt;
bool __T;
void up(int &x){if (x>=P) x-=P;}
void add(int u,int v){
  Go[++cnt]=v;Next[cnt]=End[u];End[u]=cnt;
}
int Root(int S){
  int h=0,t=1;Q[1]=S;father[S]=0;
  while (h<t){
    int x=Q[++h];size[x]=1;son[x]=0;
    for (int i=End[x],y;i;i=Next[i])
      if ((y=Go[i])!=father[x])
        father[Q[++t]=y]=x;
  }
  int ret=0;son[0]=n+1;
  for (int i=t;i;i--){
    int x=Q[i];
    son[x]=max(son[x],t-size[x]);
    if (son[x]<son[ret]) ret=x;
    if (father[x]) 
      size[father[x]]+=size[x],son[father[x]]=max(son[father[x]],size[x]);
  }return ret;
}
void DFS(int x,int fa){
	size[x]=1;
  for (int i=End[x],y;i;i=Next[i])
    if ((y=Go[i])!=fa){
      DFS(y,x),size[x]+=size[y];
      if (x==root) b[++m]=size[y];
    }
}
int solve(int n){
	C[0][0]=1;
	for (int i=1;i<=n;i++){
		C[i][0]=1;
		for (int j=1;j<=i;j++)
		  up(C[i][j]=C[i-1][j-1]+C[i-1][j]);
	}
	fac[0]=1;
	for (int i=1;i<=n;i++)
	  fac[i]=1ll*fac[i-1]*i%P;
	memset(F,0,sizeof(F));
  F[0][0]=1;
  for (int i=1;i<=m;i++) sum[i]=sum[i-1]+b[i];
  for (int i=0;i<m;i++)
    for (int j=0;j<=sum[i];j++)
      if (F[i][j])
        for (int k=0;k<=b[i+1];k++)
          up(F[i+1][k+j]+=1ll*F[i][j]*C[b[i+1]][k]%P*C[b[i+1]][k]%P*fac[k]%P);
  int ans=0;
  for (int i=0;i<=n;i++){
    int tmp=1ll*F[m][i]*fac[n-i]%P;
    if (i&1^1) up(ans+=tmp);else up(ans+=P-tmp);
  }
  return ans;
	/*b1+b2..+b_m=n
	//Ã¿Ò»¸öµã±ØÐëÖ¸Ïò±ð´¦£¬ÎÊ·½°¸Êý 
	F[0][0]=1;
	for (int i=1;i<=m;i++) sum[i]=sum[i-1]+b[i];
	for (int i=0;i<m;i++)
	  for (int j=0;j<=sum[i];j++)
	    if (F[i][j])
	      for (int k=0;k<=min(j,b[i+1]);k++)
	        up(F[i+1][j-k+b[i+1]]+=1ll*F[i][j]*C[j][k]%P*C[n-sum[i+1]][b[i+1]-k]%P);
	return F[m][1];*/ 
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<n;i++){
	  int x,y;scanf("%d%d",&x,&y);
	  add(x,y);add(y,x);
	}
	//n=3;add(1,2);add(2,1);add(2,3);add(3,2);
	root=Root(1);
	DFS(root,0);
	int ans1=solve(n-1);
	b[++m]=1;
	int ans2=solve(n);
	printf("%d\n",(ans1+ans2)%P);
}
### Prompt

Please create a solution in Cpp 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 N 5005
#define pb push_back
using namespace std;
const int P=1e9+7;
bool __S;
int size[N],son[N],Q[N],father[N];
int b[N],sum[N],C[N][N],F[N][N],fac[N],n,m,root;
int Go[N<<1],Next[N<<1],Value[N<<1],End[N],cnt;
bool __T;
void up(int &x){if (x>=P) x-=P;}
void add(int u,int v){
  Go[++cnt]=v;Next[cnt]=End[u];End[u]=cnt;
}
int Root(int S){
  int h=0,t=1;Q[1]=S;father[S]=0;
  while (h<t){
    int x=Q[++h];size[x]=1;son[x]=0;
    for (int i=End[x],y;i;i=Next[i])
      if ((y=Go[i])!=father[x])
        father[Q[++t]=y]=x;
  }
  int ret=0;son[0]=n+1;
  for (int i=t;i;i--){
    int x=Q[i];
    son[x]=max(son[x],t-size[x]);
    if (son[x]<son[ret]) ret=x;
    if (father[x]) 
      size[father[x]]+=size[x],son[father[x]]=max(son[father[x]],size[x]);
  }return ret;
}
void DFS(int x,int fa){
	size[x]=1;
  for (int i=End[x],y;i;i=Next[i])
    if ((y=Go[i])!=fa){
      DFS(y,x),size[x]+=size[y];
      if (x==root) b[++m]=size[y];
    }
}
int solve(int n){
	C[0][0]=1;
	for (int i=1;i<=n;i++){
		C[i][0]=1;
		for (int j=1;j<=i;j++)
		  up(C[i][j]=C[i-1][j-1]+C[i-1][j]);
	}
	fac[0]=1;
	for (int i=1;i<=n;i++)
	  fac[i]=1ll*fac[i-1]*i%P;
	memset(F,0,sizeof(F));
  F[0][0]=1;
  for (int i=1;i<=m;i++) sum[i]=sum[i-1]+b[i];
  for (int i=0;i<m;i++)
    for (int j=0;j<=sum[i];j++)
      if (F[i][j])
        for (int k=0;k<=b[i+1];k++)
          up(F[i+1][k+j]+=1ll*F[i][j]*C[b[i+1]][k]%P*C[b[i+1]][k]%P*fac[k]%P);
  int ans=0;
  for (int i=0;i<=n;i++){
    int tmp=1ll*F[m][i]*fac[n-i]%P;
    if (i&1^1) up(ans+=tmp);else up(ans+=P-tmp);
  }
  return ans;
	/*b1+b2..+b_m=n
	//Ã¿Ò»¸öµã±ØÐëÖ¸Ïò±ð´¦£¬ÎÊ·½°¸Êý 
	F[0][0]=1;
	for (int i=1;i<=m;i++) sum[i]=sum[i-1]+b[i];
	for (int i=0;i<m;i++)
	  for (int j=0;j<=sum[i];j++)
	    if (F[i][j])
	      for (int k=0;k<=min(j,b[i+1]);k++)
	        up(F[i+1][j-k+b[i+1]]+=1ll*F[i][j]*C[j][k]%P*C[n-sum[i+1]][b[i+1]-k]%P);
	return F[m][1];*/ 
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<n;i++){
	  int x,y;scanf("%d%d",&x,&y);
	  add(x,y);add(y,x);
	}
	//n=3;add(1,2);add(2,1);add(2,3);add(3,2);
	root=Root(1);
	DFS(root,0);
	int ans1=solve(n-1);
	b[++m]=1;
	int ans2=solve(n);
	printf("%d\n",(ans1+ans2)%P);
}
```