#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
#define ref(i,x,y)for(int i=x;i<=y;++i)
const int N=5001,mod=1e9+7;typedef long long LL;
int n,m,x,y,o,cnt,a[N],head[N],sz[N],f[2][N],c[N][N],p[N][N],F[N];
struct xint{int to,next;}e[N*2];
void add(int x,int y){e[++cnt]=(xint){y,head[x]};head[x]=cnt;}
void Add(int x,int y){add(x,y);add(y,x);}
int solve(int M){
	memset(f,0,sizeof f);
	F[0]=1;
	ref(i,1,n)F[i]=(LL)F[i-1]*i%mod;
	ref(i,0,n)c[i][0]=p[i][0]=1;
	ref(i,1,n)ref(j,1,i)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
	ref(i,1,n)ref(j,1,i)p[i][j]=(LL)p[i][j-1]*(i-j+1)%mod;
	f[0][0]=1;int sum=0;
	ref(i,1,M){
		ref(j,0,sum){
			LL S=f[0][j];if(!S)continue;
			ref(k,0,a[i]){
				f[1][j+k]+=S*c[a[i]][k]%mod*p[a[i]][k]%mod;
				if(f[1][j+k]>=mod)f[1][j+k]-=mod;
			}
		}
		sum+=a[i];
		ref(j,0,sum)f[0][j]=f[1][j],f[1][j]=0;
	}
	int res=0;
	ref(i,0,sum)if(i&1)res=(res+mod-(LL)f[0][i]*F[sum-i]%mod)%mod;
		else res=(res+(LL)f[0][i]*F[sum-i]%mod)%mod;
	return res;
}
void work(int f,int x){
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].to;if(y==f)continue;
		a[++m]=sz[y];
	}
	if(x!=1)a[++m]=n-sz[x];a[m+1]=1;
	int ans=(solve(m)+solve(m+1))%mod;
	//ref(i,1,m)ref(j,2,a[i])ans=(LL)ans*j%mod;
	printf("%d\n",ans);
	exit(0);
}
void dfs(int f,int x){
	bool flag=1;sz[x]=1;
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].to;if(y==f)continue;
		dfs(x,y);sz[x]+=sz[y];if(sz[y]>n/2)flag=0;
	}
	if(n-sz[x]>n/2)flag=0;if(flag)work(f,x);
}
int main(){
	scanf("%d",&n);
	ref(i,2,n){scanf("%d%d",&x,&y);Add(x,y);}
	dfs(0,1);printf("0\n");
}
### 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 <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
#define ref(i,x,y)for(int i=x;i<=y;++i)
const int N=5001,mod=1e9+7;typedef long long LL;
int n,m,x,y,o,cnt,a[N],head[N],sz[N],f[2][N],c[N][N],p[N][N],F[N];
struct xint{int to,next;}e[N*2];
void add(int x,int y){e[++cnt]=(xint){y,head[x]};head[x]=cnt;}
void Add(int x,int y){add(x,y);add(y,x);}
int solve(int M){
	memset(f,0,sizeof f);
	F[0]=1;
	ref(i,1,n)F[i]=(LL)F[i-1]*i%mod;
	ref(i,0,n)c[i][0]=p[i][0]=1;
	ref(i,1,n)ref(j,1,i)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
	ref(i,1,n)ref(j,1,i)p[i][j]=(LL)p[i][j-1]*(i-j+1)%mod;
	f[0][0]=1;int sum=0;
	ref(i,1,M){
		ref(j,0,sum){
			LL S=f[0][j];if(!S)continue;
			ref(k,0,a[i]){
				f[1][j+k]+=S*c[a[i]][k]%mod*p[a[i]][k]%mod;
				if(f[1][j+k]>=mod)f[1][j+k]-=mod;
			}
		}
		sum+=a[i];
		ref(j,0,sum)f[0][j]=f[1][j],f[1][j]=0;
	}
	int res=0;
	ref(i,0,sum)if(i&1)res=(res+mod-(LL)f[0][i]*F[sum-i]%mod)%mod;
		else res=(res+(LL)f[0][i]*F[sum-i]%mod)%mod;
	return res;
}
void work(int f,int x){
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].to;if(y==f)continue;
		a[++m]=sz[y];
	}
	if(x!=1)a[++m]=n-sz[x];a[m+1]=1;
	int ans=(solve(m)+solve(m+1))%mod;
	//ref(i,1,m)ref(j,2,a[i])ans=(LL)ans*j%mod;
	printf("%d\n",ans);
	exit(0);
}
void dfs(int f,int x){
	bool flag=1;sz[x]=1;
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].to;if(y==f)continue;
		dfs(x,y);sz[x]+=sz[y];if(sz[y]>n/2)flag=0;
	}
	if(n-sz[x]>n/2)flag=0;if(flag)work(f,x);
}
int main(){
	scanf("%d",&n);
	ref(i,2,n){scanf("%d%d",&x,&y);Add(x,y);}
	dfs(0,1);printf("0\n");
}
```