#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int mo=1000000007;
int t,b[5005],x,y,n,X,Z,s[5005]; LL f[5005],F[5005],w[5005][5005];
vector <int> a[5005];
LL po(LL x,int y){
	LL z=1;
	for (;y;y>>=1,x=x*x%mo)
	if (y&1) z=z*x%mo;
	return z;
}
void dfs(int x,int y){
	s[x]=1; int z=0;
	for (int i=0;i<a[x].size();++i)
	if (a[x][i]!=y) dfs(a[x][i],x),s[x]+=s[a[x][i]],z=max(z,s[a[x][i]]);
	z=max(z,n-s[x]);
	if (z<Z) Z=z,X=x;
}
LL C(int x,int y){
	return f[x]*F[y]%mo*F[x-y]%mo;
}
int main(){
	scanf("%d",&n); f[0]=1;
	for (int i=1;i<=n;++i) f[i]=f[i-1]*i%mo;
	F[n]=po(f[n],mo-2);
	for (int i=n-1;~i;--i) F[i]=F[i+1]*(i+1)%mo;
	for (int i=1;i<n;++i){
		scanf("%d%d",&x,&y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	Z=n+10; dfs(1,0);
	for (int i=1;i<=n;++i)
	if (s[i]*2==n){
		printf("%lld\n",f[s[i]]*f[s[i]]%mo);
		return 0;
	}
	for (int i=0;i<a[X].size();++i) b[++t]=s[a[X][i]];
	for (int i=1;i<=t;++i) if (b[i]>s[X]) b[i]=n-s[X];
	b[++t]=1; X=0; w[0][0]=1;
	for (int i=1;i<=t;++i){
		for (int k=0;k<=b[i];++k)
		for (int j=0;j<=X;++j)
		(w[i][j+k]+=w[i-1][j]*C(b[i],k)%mo*C(b[i],k)%mo*f[k]%mo)%=mo;
		X+=b[i];
	}
	for (int i=0;i<=X;++i) (w[t][i]*=f[n-i])%=mo;
	for (int i=X;~i;--i)
		for (int j=i+1;j<=X;++j) (w[t][i]-=w[t][j]*C(j,i)%mo)%=mo;
	--t;
	for (int i=0;i<n;++i) (w[t][i]*=f[n-i-1])%=mo;
	for (int i=n-1;~i;--i)
		for (int j=i+1;j<n;++j) (w[t][i]-=w[t][j]*C(j,i)%mo)%=mo;
	printf("%lld\n",((w[t][0]+w[t+1][0])%mo+mo)%mo);
	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 <bits/stdc++.h>
#define LL long long
using namespace std;
const int mo=1000000007;
int t,b[5005],x,y,n,X,Z,s[5005]; LL f[5005],F[5005],w[5005][5005];
vector <int> a[5005];
LL po(LL x,int y){
	LL z=1;
	for (;y;y>>=1,x=x*x%mo)
	if (y&1) z=z*x%mo;
	return z;
}
void dfs(int x,int y){
	s[x]=1; int z=0;
	for (int i=0;i<a[x].size();++i)
	if (a[x][i]!=y) dfs(a[x][i],x),s[x]+=s[a[x][i]],z=max(z,s[a[x][i]]);
	z=max(z,n-s[x]);
	if (z<Z) Z=z,X=x;
}
LL C(int x,int y){
	return f[x]*F[y]%mo*F[x-y]%mo;
}
int main(){
	scanf("%d",&n); f[0]=1;
	for (int i=1;i<=n;++i) f[i]=f[i-1]*i%mo;
	F[n]=po(f[n],mo-2);
	for (int i=n-1;~i;--i) F[i]=F[i+1]*(i+1)%mo;
	for (int i=1;i<n;++i){
		scanf("%d%d",&x,&y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	Z=n+10; dfs(1,0);
	for (int i=1;i<=n;++i)
	if (s[i]*2==n){
		printf("%lld\n",f[s[i]]*f[s[i]]%mo);
		return 0;
	}
	for (int i=0;i<a[X].size();++i) b[++t]=s[a[X][i]];
	for (int i=1;i<=t;++i) if (b[i]>s[X]) b[i]=n-s[X];
	b[++t]=1; X=0; w[0][0]=1;
	for (int i=1;i<=t;++i){
		for (int k=0;k<=b[i];++k)
		for (int j=0;j<=X;++j)
		(w[i][j+k]+=w[i-1][j]*C(b[i],k)%mo*C(b[i],k)%mo*f[k]%mo)%=mo;
		X+=b[i];
	}
	for (int i=0;i<=X;++i) (w[t][i]*=f[n-i])%=mo;
	for (int i=X;~i;--i)
		for (int j=i+1;j<=X;++j) (w[t][i]-=w[t][j]*C(j,i)%mo)%=mo;
	--t;
	for (int i=0;i<n;++i) (w[t][i]*=f[n-i-1])%=mo;
	for (int i=n-1;~i;--i)
		for (int j=i+1;j<n;++j) (w[t][i]-=w[t][j]*C(j,i)%mo)%=mo;
	printf("%lld\n",((w[t][0]+w[t+1][0])%mo+mo)%mo);
	return 0;
}
```