#include<bits/stdc++.h>
using namespace std;

const int N=5010,mod=1000000007;
typedef long long ll;
int ksm(ll a,int b,int c=1){
	for(;b;b/=2,a=a*a%mod)
		if(b&1)c=c*a%mod;
	return c;
}
int jc[N],jc2[N];
void Init(){
	jc[0]=jc2[0]=1;
	for(int i=1;i<N;++i)jc[i]=(ll)jc[i-1]*i%mod,jc2[i]=ksm(i,mod-2,jc2[i-1]);
}
int C(int n,int k){return (ll)jc[n]*jc2[k]%mod*jc2[n-k]%mod;}
int n,dp[2][N],sz[N],rt,T,ans;
vector<int>g[N];

void dfs(int x,int fa=-1){
	int mx=0;sz[x]=1;
	for(int i:g[x])if(i!=fa){
		dfs(i,x);sz[x]+=sz[i];
		mx=max(mx,sz[i]);
	}
	mx=max(mx,n-sz[x]);
	if(!rt&&mx*2<=n)rt=x;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;Init();
	for(int i=1;i<n;++i){
		int x,y;cin>>x>>y;
		g[x].push_back(y);g[y].push_back(x);
	}
	dfs(1);dfs(rt);
	dp[0][0]=1;
	int sum=0;
	for(int i:g[rt]){
		T^=1;memset(dp[T],0,sizeof dp[T]);
		for(int j=0;j<=sum;++j)if(dp[!T][j])
			for(int k=0;k<=sz[i];++k)
				dp[T][j+k]=(dp[T][j+k]+(ll)dp[!T][j]*C(sz[i],k)%mod*C(sz[i],k)%mod*jc[k])%mod;
		sum+=sz[i];
	}
	for(int i=0;i<=n;++i){
		int tmp=(ll)dp[T][i]*jc[n-i]%mod;
		if(i&1)ans=(ans-tmp+mod)%mod;
		else ans=(ans+tmp)%mod;
	}
	cout<<ans<<'\n';
	return 0;
}

### Prompt

Your challenge is to write 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>
using namespace std;

const int N=5010,mod=1000000007;
typedef long long ll;
int ksm(ll a,int b,int c=1){
	for(;b;b/=2,a=a*a%mod)
		if(b&1)c=c*a%mod;
	return c;
}
int jc[N],jc2[N];
void Init(){
	jc[0]=jc2[0]=1;
	for(int i=1;i<N;++i)jc[i]=(ll)jc[i-1]*i%mod,jc2[i]=ksm(i,mod-2,jc2[i-1]);
}
int C(int n,int k){return (ll)jc[n]*jc2[k]%mod*jc2[n-k]%mod;}
int n,dp[2][N],sz[N],rt,T,ans;
vector<int>g[N];

void dfs(int x,int fa=-1){
	int mx=0;sz[x]=1;
	for(int i:g[x])if(i!=fa){
		dfs(i,x);sz[x]+=sz[i];
		mx=max(mx,sz[i]);
	}
	mx=max(mx,n-sz[x]);
	if(!rt&&mx*2<=n)rt=x;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;Init();
	for(int i=1;i<n;++i){
		int x,y;cin>>x>>y;
		g[x].push_back(y);g[y].push_back(x);
	}
	dfs(1);dfs(rt);
	dp[0][0]=1;
	int sum=0;
	for(int i:g[rt]){
		T^=1;memset(dp[T],0,sizeof dp[T]);
		for(int j=0;j<=sum;++j)if(dp[!T][j])
			for(int k=0;k<=sz[i];++k)
				dp[T][j+k]=(dp[T][j+k]+(ll)dp[!T][j]*C(sz[i],k)%mod*C(sz[i],k)%mod*jc[k])%mod;
		sum+=sz[i];
	}
	for(int i=0;i<=n;++i){
		int tmp=(ll)dp[T][i]*jc[n-i]%mod;
		if(i&1)ans=(ans-tmp+mod)%mod;
		else ans=(ans+tmp)%mod;
	}
	cout<<ans<<'\n';
	return 0;
}

```