//by yjz
#include<bits/stdc++.h>
using namespace std;
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
#define bged(v) (v).begin(),(v).end()
#define foreach(it,s) for(__typeof((s).begin()) it=(s).begin();it!=(s).end();it++)
typedef long long ll;
const int Imx=2147483647;
const ll Lbig=2e18;
const int mod=1e9+7;
//My i/o stream
struct fastio
{
	char s[100000];
	int it,len;
	fastio(){it=len=0;}
	inline char get()
	{
		if(it<len)return s[it++];it=0;
		len=fread(s,1,100000,stdin);
		if(len==0)return EOF;else return s[it++];
	}
	bool notend()
	{
		char c=get();
		while(c==' '||c=='\n')c=get();
		if(it>0)it--;
		return c!=EOF;
	}
}_buff;
#define geti(x) x=getnum()
#define getii(x,y) geti(x),geti(y)
#define getiii(x,y,z) getii(x,y),geti(z)
#define puti(x) putnum(x),putchar(' ')
#define putii(x,y) puti(x),puti(y)
#define putiii(x,y,z) putii(x,y),puti(z)
#define putsi(x) putnum(x),putchar('\n')
#define putsii(x,y) puti(x),putsi(y)
#define putsiii(x,y,z) putii(x,y),putsi(z)
inline ll getnum()
{
	ll r=0;bool ng=0;char c;c=_buff.get();
	while(c!='-'&&(c<'0'||c>'9'))c=_buff.get();
	if(c=='-')ng=1,c=_buff.get();
	while(c>='0'&&c<='9')r=r*10+c-'0',c=_buff.get();
	return ng?-r:r;
}
template<class T> inline void putnum(T x)
{
	if(x<0)putchar('-'),x=-x;
	register short a[20]={},sz=0;
	while(x)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1;i>=0;i--)putchar('0'+a[i]);
}
inline char getreal(){char c=_buff.get();while(c==' '||c=='\n')c=_buff.get();return c;}
int n;
vector<pair<int,int> > con[5111];
int sz[5111],pc[5111];
ll ans;
void dfs(int x,int pre=-1)
{
	sz[x]=1;
	for(int i=0;i<con[x].size();i++)
	{
		int u=con[x][i].FF;
		if(pre!=u)
		{
			dfs(u,x);
			sz[x]+=sz[u];
			pc[u]=con[x][i].SS;
			ans+=1ll*pc[u]*min(sz[u],n-sz[u])*2;
		}
	}
}
ll qpow(ll x,ll k){return k==0?1:qpow(x*x%mod,k>>1)*(k&1?x:1)%mod;}
ll fac[5111],ifac[5111];
ll C(int x,int y){return x<y?0:fac[x]*ifac[y]%mod*ifac[x-y]%mod;}
ll dp[5111],ndp[5111];
int main()
{
	fac[0]=1;
	for(int i=1;i<=5005;i++)fac[i]=fac[i-1]*i%mod;
	ifac[5005]=qpow(fac[5005],mod-2);
	for(int i=5004;i>=0;i--)ifac[i]=ifac[i+1]*(i+1)%mod;
	geti(n);
	for(int i=1;i<n;i++)
	{
		int x,y,c;
		getii(x,y);
		c=1;
		con[x].PB(MP(y,c));
		con[y].PB(MP(x,c));
	}
	dfs(1);
	int mn=n+1,mnid=-1;
	for(int i=1;i<=n;i++)
	{
		if(sz[i]*2==n)
		{
			cout<<fac[n/2]*fac[n/2]%mod<<endl;
			return 0;
		}
		if(sz[i]*2>=n)
		{
			if(sz[i]<mn)mn=sz[i],mnid=i;
		}
	}
	dfs(mnid);
	dp[0]=1;
	for(int i=0;i<con[mnid].size();i++)
	{
		int u=con[mnid][i].FF;
		memset(ndp,0,sizeof(ndp));
		int m=sz[u];
//		cerr<<"m="<<m<<endl;
		for(int j=0;j<=m;j++)
		{
			ll coef=C(m,j)*C(m,j)%mod*fac[j]%mod;
			if(j&1)coef=(mod-coef)%mod;
			for(int t=0;t<=n;t++)
			{
				if(!dp[t])continue;
				ndp[j+t]+=dp[t]*coef%mod;
			}
		}
		for(int t=0;t<=n;t++)dp[t]=ndp[t]%mod;
	}
//	for(int t=0;t<=n;t++)cerr<<dp[t]<<" ";cerr<<endl;
	ll ans=0;
	for(int i=0;i<=n;i++)ans=(ans+dp[i]*fac[n-i]%mod)%mod;
	cout<<ans<<endl;
	return 0;
}
### Prompt

Develop a solution in cpp to the problem described below:

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
//by yjz
#include<bits/stdc++.h>
using namespace std;
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
#define bged(v) (v).begin(),(v).end()
#define foreach(it,s) for(__typeof((s).begin()) it=(s).begin();it!=(s).end();it++)
typedef long long ll;
const int Imx=2147483647;
const ll Lbig=2e18;
const int mod=1e9+7;
//My i/o stream
struct fastio
{
	char s[100000];
	int it,len;
	fastio(){it=len=0;}
	inline char get()
	{
		if(it<len)return s[it++];it=0;
		len=fread(s,1,100000,stdin);
		if(len==0)return EOF;else return s[it++];
	}
	bool notend()
	{
		char c=get();
		while(c==' '||c=='\n')c=get();
		if(it>0)it--;
		return c!=EOF;
	}
}_buff;
#define geti(x) x=getnum()
#define getii(x,y) geti(x),geti(y)
#define getiii(x,y,z) getii(x,y),geti(z)
#define puti(x) putnum(x),putchar(' ')
#define putii(x,y) puti(x),puti(y)
#define putiii(x,y,z) putii(x,y),puti(z)
#define putsi(x) putnum(x),putchar('\n')
#define putsii(x,y) puti(x),putsi(y)
#define putsiii(x,y,z) putii(x,y),putsi(z)
inline ll getnum()
{
	ll r=0;bool ng=0;char c;c=_buff.get();
	while(c!='-'&&(c<'0'||c>'9'))c=_buff.get();
	if(c=='-')ng=1,c=_buff.get();
	while(c>='0'&&c<='9')r=r*10+c-'0',c=_buff.get();
	return ng?-r:r;
}
template<class T> inline void putnum(T x)
{
	if(x<0)putchar('-'),x=-x;
	register short a[20]={},sz=0;
	while(x)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1;i>=0;i--)putchar('0'+a[i]);
}
inline char getreal(){char c=_buff.get();while(c==' '||c=='\n')c=_buff.get();return c;}
int n;
vector<pair<int,int> > con[5111];
int sz[5111],pc[5111];
ll ans;
void dfs(int x,int pre=-1)
{
	sz[x]=1;
	for(int i=0;i<con[x].size();i++)
	{
		int u=con[x][i].FF;
		if(pre!=u)
		{
			dfs(u,x);
			sz[x]+=sz[u];
			pc[u]=con[x][i].SS;
			ans+=1ll*pc[u]*min(sz[u],n-sz[u])*2;
		}
	}
}
ll qpow(ll x,ll k){return k==0?1:qpow(x*x%mod,k>>1)*(k&1?x:1)%mod;}
ll fac[5111],ifac[5111];
ll C(int x,int y){return x<y?0:fac[x]*ifac[y]%mod*ifac[x-y]%mod;}
ll dp[5111],ndp[5111];
int main()
{
	fac[0]=1;
	for(int i=1;i<=5005;i++)fac[i]=fac[i-1]*i%mod;
	ifac[5005]=qpow(fac[5005],mod-2);
	for(int i=5004;i>=0;i--)ifac[i]=ifac[i+1]*(i+1)%mod;
	geti(n);
	for(int i=1;i<n;i++)
	{
		int x,y,c;
		getii(x,y);
		c=1;
		con[x].PB(MP(y,c));
		con[y].PB(MP(x,c));
	}
	dfs(1);
	int mn=n+1,mnid=-1;
	for(int i=1;i<=n;i++)
	{
		if(sz[i]*2==n)
		{
			cout<<fac[n/2]*fac[n/2]%mod<<endl;
			return 0;
		}
		if(sz[i]*2>=n)
		{
			if(sz[i]<mn)mn=sz[i],mnid=i;
		}
	}
	dfs(mnid);
	dp[0]=1;
	for(int i=0;i<con[mnid].size();i++)
	{
		int u=con[mnid][i].FF;
		memset(ndp,0,sizeof(ndp));
		int m=sz[u];
//		cerr<<"m="<<m<<endl;
		for(int j=0;j<=m;j++)
		{
			ll coef=C(m,j)*C(m,j)%mod*fac[j]%mod;
			if(j&1)coef=(mod-coef)%mod;
			for(int t=0;t<=n;t++)
			{
				if(!dp[t])continue;
				ndp[j+t]+=dp[t]*coef%mod;
			}
		}
		for(int t=0;t<=n;t++)dp[t]=ndp[t]%mod;
	}
//	for(int t=0;t<=n;t++)cerr<<dp[t]<<" ";cerr<<endl;
	ll ans=0;
	for(int i=0;i<=n;i++)ans=(ans+dp[i]*fac[n-i]%mod)%mod;
	cout<<ans<<endl;
	return 0;
}
```