#include<bits/stdc++.h>

using namespace std;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0' || '9'<ch){if(ch=='-')f=-1;ch=getchar();}
	while('0'<=ch && ch<='9')x=x*10+(ch^48),ch=getchar();
	return x*f;
}

inline void chkmax(int &a,int b){if(a<b)a=b;}
inline void chkmin(int &a,int b){if(a>b)a=b;}

typedef long long ll;
const int N=5009;
const int md=1e9+7;

int n,root[3],fa[N],rtop;
vector<int> g[N];
ll fac[N],inv[N],c[N][N];
ll f[N],siz[N];

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

inline void dfs(int u)
{
	siz[u]=1;int mx=0;
	for(int i=0,e=g[u].size();i<e;i++)
		if(g[u][i]!=fa[u])
		{
			fa[g[u][i]]=u;
			dfs(g[u][i]);
			siz[u]+=siz[g[u][i]];
			chkmax(mx,siz[g[u][i]]);
		}
	chkmax(mx,n-siz[u]);
	if(mx*2<=n)root[++rtop]=u;
}

inline void init()
{
	fac[0]=1;
	for(ll i=1;i<N;i++)
		fac[i]=fac[i-1]*i%md;
	inv[N-1]=qpow(fac[N-1],md-2);
	for(ll i=N-1;i>=1;i--)
		inv[i-1]=inv[i]*i%md;

	c[0][0]=1;
	for(int i=1;i<N;i++)
	{
		c[i][0]=c[i][i]=1;
		for(int j=1;j<=i;j++)
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%md;
	}
}

int main()
{
	if(fopen("vj.in","r"))
	{
		freopen("vj.in","r",stdin);
		freopen("vj.out","w",stdout);
	}

	init();
	n=read();
	for(int i=1,u,v;i<n;i++)
	{
		u=read();v=read();
		g[u].push_back(v);
		g[v].push_back(u);
	}

	dfs(1);
	if(rtop==2)
	{
		printf("%lld\n",fac[n/2]*fac[n/2]%md);
		return 0;
	}
	
	memset(fa,0,sizeof(fa));

	rtop=0;
	dfs(root[1]);

	f[0]=1;
	for(int x=0,e=g[root[1]].size();x<e;x++)
	{
		ll cur=siz[g[root[1]][x]];
		for(int i=n;i;i--)
			for(int j=i-1;j>=0 && i-j<=cur;j--)
				(f[i]+=f[j]*c[cur][i-j]%md*c[cur][i-j]%md*fac[i-j]%md)%=md;
	}

	ll ans=0;
	for(int i=0;i<=n;i++)
		ans=(ans+(i&1?-1:1)*f[i]*fac[n-i]%md+md)%md;
	printf("%lld\n",ans);
	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>

using namespace std;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0' || '9'<ch){if(ch=='-')f=-1;ch=getchar();}
	while('0'<=ch && ch<='9')x=x*10+(ch^48),ch=getchar();
	return x*f;
}

inline void chkmax(int &a,int b){if(a<b)a=b;}
inline void chkmin(int &a,int b){if(a>b)a=b;}

typedef long long ll;
const int N=5009;
const int md=1e9+7;

int n,root[3],fa[N],rtop;
vector<int> g[N];
ll fac[N],inv[N],c[N][N];
ll f[N],siz[N];

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

inline void dfs(int u)
{
	siz[u]=1;int mx=0;
	for(int i=0,e=g[u].size();i<e;i++)
		if(g[u][i]!=fa[u])
		{
			fa[g[u][i]]=u;
			dfs(g[u][i]);
			siz[u]+=siz[g[u][i]];
			chkmax(mx,siz[g[u][i]]);
		}
	chkmax(mx,n-siz[u]);
	if(mx*2<=n)root[++rtop]=u;
}

inline void init()
{
	fac[0]=1;
	for(ll i=1;i<N;i++)
		fac[i]=fac[i-1]*i%md;
	inv[N-1]=qpow(fac[N-1],md-2);
	for(ll i=N-1;i>=1;i--)
		inv[i-1]=inv[i]*i%md;

	c[0][0]=1;
	for(int i=1;i<N;i++)
	{
		c[i][0]=c[i][i]=1;
		for(int j=1;j<=i;j++)
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%md;
	}
}

int main()
{
	if(fopen("vj.in","r"))
	{
		freopen("vj.in","r",stdin);
		freopen("vj.out","w",stdout);
	}

	init();
	n=read();
	for(int i=1,u,v;i<n;i++)
	{
		u=read();v=read();
		g[u].push_back(v);
		g[v].push_back(u);
	}

	dfs(1);
	if(rtop==2)
	{
		printf("%lld\n",fac[n/2]*fac[n/2]%md);
		return 0;
	}
	
	memset(fa,0,sizeof(fa));

	rtop=0;
	dfs(root[1]);

	f[0]=1;
	for(int x=0,e=g[root[1]].size();x<e;x++)
	{
		ll cur=siz[g[root[1]][x]];
		for(int i=n;i;i--)
			for(int j=i-1;j>=0 && i-j<=cur;j--)
				(f[i]+=f[j]*c[cur][i-j]%md*c[cur][i-j]%md*fac[i-j]%md)%=md;
	}

	ll ans=0;
	for(int i=0;i<=n;i++)
		ans=(ans+(i&1?-1:1)*f[i]*fac[n-i]%md+md)%md;
	printf("%lld\n",ans);
	return 0;
}

```