#include <bits/stdc++.h>
#ifdef DEMETRIO
#define deb(...) fprintf(stderr,__VA_ARGS__)
#define deb1(x) cerr << #x << " = " << x << endl
#else
#define deb(...) 0
#define deb1(x) 0
#endif
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
#define SZ(x) ((int)x.size())
#define MOD 1000000007
using namespace std;
typedef long long ll;

vector<int> g[5005];int n;
int s[5005],fa[5005];
vector<int> c,v;

void dfs(int x, int f){
	int m=0;
	s[x]=1;
	for(int y:g[x]){
		if(y==f)continue;
		dfs(y,x);
		s[x]+=s[y];
		m=max(m,s[y]);
	}
	m=max(m,n-s[x]);
	if(m<=n/2)c.pb(x);
}

int dp[5005][5005];
int cc[5005][5005];

int f(int k, int q){
	if(dp[k][q]>=0)return dp[k][q];
	int r=0;
	if(k==SZ(v))r=q==0;
	else {
		int m=1;
		fore(i,0,min(q,v[k])+1){
			r+=1LL*((1LL*m*f(k+1,q-i))%MOD*cc[v[k]][i])%MOD;
			r%=MOD;
			m=(1LL*m*(v[k]-i))%MOD;
		}
	}
	return dp[k][q]=r;
}

int main(){
	memset(dp,-1,sizeof(dp));
	fa[0]=1;
	fore(i,1,5005)fa[i]=(1LL*fa[i-1]*i)%MOD;
	fore(i,0,5005){
		cc[i][0]=cc[i][i]=1;
		fore(j,1,i)cc[i][j]=(cc[i-1][j-1]+cc[i-1][j])%MOD;
	}
	scanf("%d",&n);
	fore(i,1,n){
		int x,y;
		scanf("%d%d",&x,&y);x--;y--;
		g[x].pb(y);g[y].pb(x);
	}
	dfs(0,-1);
	if(SZ(c)==2){printf("%lld\n",(1LL*fa[n/2]*fa[n/2])%MOD);return 0;}
	assert(SZ(c)==1);
	int x=c[0];
	if(x)v.pb(n-s[x]);
	for(int y:g[x])if(s[y]<s[x])v.pb(s[y]);
	int r=0;
	fore(i,0,n){
		int a=(1LL*fa[n-i]*f(0,i))%MOD;
		if(i%2==0)r+=a;
		else r+=MOD-a;
		r%=MOD;
	}
	printf("%d\n",r);
	return 0;
}
### Prompt

Please formulate a CPP solution 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>
#ifdef DEMETRIO
#define deb(...) fprintf(stderr,__VA_ARGS__)
#define deb1(x) cerr << #x << " = " << x << endl
#else
#define deb(...) 0
#define deb1(x) 0
#endif
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
#define SZ(x) ((int)x.size())
#define MOD 1000000007
using namespace std;
typedef long long ll;

vector<int> g[5005];int n;
int s[5005],fa[5005];
vector<int> c,v;

void dfs(int x, int f){
	int m=0;
	s[x]=1;
	for(int y:g[x]){
		if(y==f)continue;
		dfs(y,x);
		s[x]+=s[y];
		m=max(m,s[y]);
	}
	m=max(m,n-s[x]);
	if(m<=n/2)c.pb(x);
}

int dp[5005][5005];
int cc[5005][5005];

int f(int k, int q){
	if(dp[k][q]>=0)return dp[k][q];
	int r=0;
	if(k==SZ(v))r=q==0;
	else {
		int m=1;
		fore(i,0,min(q,v[k])+1){
			r+=1LL*((1LL*m*f(k+1,q-i))%MOD*cc[v[k]][i])%MOD;
			r%=MOD;
			m=(1LL*m*(v[k]-i))%MOD;
		}
	}
	return dp[k][q]=r;
}

int main(){
	memset(dp,-1,sizeof(dp));
	fa[0]=1;
	fore(i,1,5005)fa[i]=(1LL*fa[i-1]*i)%MOD;
	fore(i,0,5005){
		cc[i][0]=cc[i][i]=1;
		fore(j,1,i)cc[i][j]=(cc[i-1][j-1]+cc[i-1][j])%MOD;
	}
	scanf("%d",&n);
	fore(i,1,n){
		int x,y;
		scanf("%d%d",&x,&y);x--;y--;
		g[x].pb(y);g[y].pb(x);
	}
	dfs(0,-1);
	if(SZ(c)==2){printf("%lld\n",(1LL*fa[n/2]*fa[n/2])%MOD);return 0;}
	assert(SZ(c)==1);
	int x=c[0];
	if(x)v.pb(n-s[x]);
	for(int y:g[x])if(s[y]<s[x])v.pb(s[y]);
	int r=0;
	fore(i,0,n){
		int a=(1LL*fa[n-i]*f(0,i))%MOD;
		if(i%2==0)r+=a;
		else r+=MOD-a;
		r%=MOD;
	}
	printf("%d\n",r);
	return 0;
}
```