#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10;
const int mod=1e9+7;

int qpow(int a,int b) {
	int ret=1;
	while(b) {
		if(b&1) ret=1ll*ret*a%mod;
		a=1ll*a*a%mod,b>>=1;
	}
	return ret;
}

int n,fac[N],ifac[N],f[N],nf[N],siz[N],g[N],mn=1e9;
vector<int> E[N];

void dfs(int u,int fa) {
	siz[u]=1;
	for(auto v:E[u])
		if(v^fa) {
			dfs(v,u),siz[u]+=siz[v];
			g[u]=max(g[u],siz[v]);
		}
	g[u]=max(g[u],n-siz[u]);
	mn=min(mn,g[u]);
}

int main() {
	cin>>n;
	for(int i=1,u,v;i<n;i++) cin>>u>>v,E[u].push_back(v),E[v].push_back(u);
	fac[0]=1;for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
	ifac[n]=qpow(fac[n],mod-2);
	for(int i=n;i;i--) ifac[i-1]=1ll*ifac[i]*i%mod;
	dfs(1,0);
	int x=0,y=0;
	for(int i=1;i<=n;i++)
		if(g[i]==mn) (x?y:x)=i;
	if(y) cout<<1ll*fac[n/2]*fac[n/2]%mod;
	else {
		f[0]=1;int sum=0,ans=0;
		for(auto u:E[x]) {
			dfs(u,x);memset(nf,0,sizeof(nf));
			for(int i=0;i<=sum;i++)
				for(int j=0;j<=siz[u];j++)
					nf[i+j]=(nf[i+j]+1ll*f[i]*fac[siz[u]]%mod*fac[siz[u]]%mod*ifac[j]%mod*ifac[siz[u]-j]%mod*ifac[siz[u]-j])%mod;
			swap(f,nf);sum+=siz[u];
		}
		for(int i=0;i<n;i++) ans=(ans+1ll*f[i]*((i&1)?mod-1:1)%mod*fac[n-i])%mod;
		cout<<ans;
	}
	return 0;
}

### Prompt

Create a solution in cpp for 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=5e3+10;
const int mod=1e9+7;

int qpow(int a,int b) {
	int ret=1;
	while(b) {
		if(b&1) ret=1ll*ret*a%mod;
		a=1ll*a*a%mod,b>>=1;
	}
	return ret;
}

int n,fac[N],ifac[N],f[N],nf[N],siz[N],g[N],mn=1e9;
vector<int> E[N];

void dfs(int u,int fa) {
	siz[u]=1;
	for(auto v:E[u])
		if(v^fa) {
			dfs(v,u),siz[u]+=siz[v];
			g[u]=max(g[u],siz[v]);
		}
	g[u]=max(g[u],n-siz[u]);
	mn=min(mn,g[u]);
}

int main() {
	cin>>n;
	for(int i=1,u,v;i<n;i++) cin>>u>>v,E[u].push_back(v),E[v].push_back(u);
	fac[0]=1;for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
	ifac[n]=qpow(fac[n],mod-2);
	for(int i=n;i;i--) ifac[i-1]=1ll*ifac[i]*i%mod;
	dfs(1,0);
	int x=0,y=0;
	for(int i=1;i<=n;i++)
		if(g[i]==mn) (x?y:x)=i;
	if(y) cout<<1ll*fac[n/2]*fac[n/2]%mod;
	else {
		f[0]=1;int sum=0,ans=0;
		for(auto u:E[x]) {
			dfs(u,x);memset(nf,0,sizeof(nf));
			for(int i=0;i<=sum;i++)
				for(int j=0;j<=siz[u];j++)
					nf[i+j]=(nf[i+j]+1ll*f[i]*fac[siz[u]]%mod*fac[siz[u]]%mod*ifac[j]%mod*ifac[siz[u]-j]%mod*ifac[siz[u]-j])%mod;
			swap(f,nf);sum+=siz[u];
		}
		for(int i=0;i<n;i++) ans=(ans+1ll*f[i]*((i&1)?mod-1:1)%mod*fac[n-i])%mod;
		cout<<ans;
	}
	return 0;
}

```