#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<vector>
using namespace std;

const int N=5005;
const int mod=1000000007;

int n,x,y,rt,mz,ans,tag;
int dp[N],sz[N],mx[N],c[N][N],fac[N];
vector<int> lev[N];

void add(int x,int y){
	lev[x].push_back(y);
	lev[y].push_back(x);
}

void dfs(int k,int pre){
	int u,j;
	sz[k]=1; mx[k]=0;
	for (j=0;j<lev[k].size();j++){
		u=lev[k][j];
		if (u==pre) continue;
		dfs(u,k);
		mx[k]=max(mx[k],sz[u]);
		sz[k]+=sz[u];
	}
	mx[k]=max(mx[k],n-sz[k]);
	if (mx[k]<mz) mz=mx[k],rt=k;
}

void init(){
	int i,j;
	c[0][0]=1; fac[0]=1;
	for (i=1;i<=n;i++){
		c[i][0]=1;
		for (j=1;j<=i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
	}
	for (i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
}

int main(){
	int i,j,l;
	scanf("%d",&n);
	init();
	for (i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		add(x,y);
	}
	mz=n; rt=0;
	dfs(1,0);
	for (i=1;i<=n;i++)
		if (mx[i]==mz&&i!=rt){
			printf("%d\n",1ll*fac[n/2]*fac[n/2]%mod);
			return 0;
		}
	dfs(rt,0);
	dp[0]=1;
	for (j=0;j<lev[rt].size();j++){
		x=lev[rt][j]; y=sz[x];
		for (i=n;i;i--)
			for (l=i-1;l>=0&&i-l<=y;l--){
				dp[i]=(dp[i]+1ll*dp[l]*c[y][i-l]%mod*c[y][i-l]%mod*fac[i-l]%mod)%mod;
			}
	}
	tag=1;
	for (i=0;i<n;i++){
		ans=(ans+1ll*tag*dp[i]*fac[n-i]%mod)%mod;
		tag*=-1;
	}
	ans=(ans+mod)%mod;
	printf("%d\n",ans);
	return 0;
}
### Prompt

In cpp, your task is to solve 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<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<vector>
using namespace std;

const int N=5005;
const int mod=1000000007;

int n,x,y,rt,mz,ans,tag;
int dp[N],sz[N],mx[N],c[N][N],fac[N];
vector<int> lev[N];

void add(int x,int y){
	lev[x].push_back(y);
	lev[y].push_back(x);
}

void dfs(int k,int pre){
	int u,j;
	sz[k]=1; mx[k]=0;
	for (j=0;j<lev[k].size();j++){
		u=lev[k][j];
		if (u==pre) continue;
		dfs(u,k);
		mx[k]=max(mx[k],sz[u]);
		sz[k]+=sz[u];
	}
	mx[k]=max(mx[k],n-sz[k]);
	if (mx[k]<mz) mz=mx[k],rt=k;
}

void init(){
	int i,j;
	c[0][0]=1; fac[0]=1;
	for (i=1;i<=n;i++){
		c[i][0]=1;
		for (j=1;j<=i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
	}
	for (i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
}

int main(){
	int i,j,l;
	scanf("%d",&n);
	init();
	for (i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		add(x,y);
	}
	mz=n; rt=0;
	dfs(1,0);
	for (i=1;i<=n;i++)
		if (mx[i]==mz&&i!=rt){
			printf("%d\n",1ll*fac[n/2]*fac[n/2]%mod);
			return 0;
		}
	dfs(rt,0);
	dp[0]=1;
	for (j=0;j<lev[rt].size();j++){
		x=lev[rt][j]; y=sz[x];
		for (i=n;i;i--)
			for (l=i-1;l>=0&&i-l<=y;l--){
				dp[i]=(dp[i]+1ll*dp[l]*c[y][i-l]%mod*c[y][i-l]%mod*fac[i-l]%mod)%mod;
			}
	}
	tag=1;
	for (i=0;i<n;i++){
		ans=(ans+1ll*tag*dp[i]*fac[n-i]%mod)%mod;
		tag*=-1;
	}
	ans=(ans+mod)%mod;
	printf("%d\n",ans);
	return 0;
}
```