#include <bits/stdc++.h>
#define N 5010
#define int long long
#define mod 1000000007
using namespace std;

inline int read()
{
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
	return x*f;
}
struct edge
{
	int v,next;
}vs[N<<1];
inline int qpow(int bas,int pw)
{
	int ret=1;
	for(;pw;pw>>=1,bas=1ll*bas*bas%mod)
		if(pw&1) ret=1ll*ret*bas%mod; return ret;
}
int n,ee,st[N],p1,s1,p2,s2;
int size[N],fac[N],inv[N],fa[N];
int bs[N],tot,F[N],G[N];
inline void addedge(int u,int v)
{
	vs[++ee].v=v;vs[ee].next=st[u];st[u]=ee;
}
inline void dfs(int rt)
{
	size[rt]=1; int mx=0;
	for(int i=st[rt];i;i=vs[i].next)
	{
		if(vs[i].v==fa[rt]) continue;
		fa[vs[i].v]=rt; dfs(vs[i].v);
		size[rt]+=size[vs[i].v];
		mx=max(mx,size[vs[i].v]);
	}
	int sd=max(mx,n-size[rt]),pd=rt;
	if(sd<s1) swap(sd,s1),swap(pd,p1);
	if(sd<s2) swap(sd,s2),swap(pd,p2);
}
inline void Add(int &x,int y)
{
	x+=y; if(x>=mod) x-=mod;
	if(x<0) x+=mod;
}
inline int C(int n,int m)
{
	return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main()
{
	fac[0]=inv[0]=1;
	for(int i=1;i<=5000;i++) fac[i]=1ll*fac[i-1]*i%mod;
	inv[5000]=qpow(fac[5000],mod-2); 
	for(int i=4999;i>=1;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
	n=read(); 
	s1=s2=n+1;
	for(int i=1;i<n;i++)
	{
		int u=read(), v=read();
		addedge(u,v); addedge(v,u);
	}
	dfs(1);
	if(!(s1^s2)){cout << 1ll*fac[n/2]*fac[n/2]%mod << endl; return 0;}
	else 
	{
		for(int i=st[p1];i;i=vs[i].next)
		{
			if(vs[i].v==fa[p1]) continue;
			bs[++tot]=size[vs[i].v];
		}
		bs[++tot]=n-size[p1]; F[0]=1;
		for(int i=1;i<=tot;i++)
		{
			for(int j=0;j<=n-1;j++) G[j]=F[j];
			for(int j=1;j<=bs[i];j++)
				for(int k=n-1;k>=j;k--) if(F[k-j])
					Add(G[k],1ll*F[k-j]*fac[bs[i]]%mod*inv[bs[i]-j]%mod*C(bs[i],j)%mod);
			for(int j=0;j<=n-1;j++) F[j]=G[j];
		}
		int Ans=fac[n];
		for(int i=1,f=-1;i<=n-1;i++,f*=-1)
			Add(Ans,f*F[i]*fac[n-i]%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
#include <bits/stdc++.h>
#define N 5010
#define int long long
#define mod 1000000007
using namespace std;

inline int read()
{
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
	return x*f;
}
struct edge
{
	int v,next;
}vs[N<<1];
inline int qpow(int bas,int pw)
{
	int ret=1;
	for(;pw;pw>>=1,bas=1ll*bas*bas%mod)
		if(pw&1) ret=1ll*ret*bas%mod; return ret;
}
int n,ee,st[N],p1,s1,p2,s2;
int size[N],fac[N],inv[N],fa[N];
int bs[N],tot,F[N],G[N];
inline void addedge(int u,int v)
{
	vs[++ee].v=v;vs[ee].next=st[u];st[u]=ee;
}
inline void dfs(int rt)
{
	size[rt]=1; int mx=0;
	for(int i=st[rt];i;i=vs[i].next)
	{
		if(vs[i].v==fa[rt]) continue;
		fa[vs[i].v]=rt; dfs(vs[i].v);
		size[rt]+=size[vs[i].v];
		mx=max(mx,size[vs[i].v]);
	}
	int sd=max(mx,n-size[rt]),pd=rt;
	if(sd<s1) swap(sd,s1),swap(pd,p1);
	if(sd<s2) swap(sd,s2),swap(pd,p2);
}
inline void Add(int &x,int y)
{
	x+=y; if(x>=mod) x-=mod;
	if(x<0) x+=mod;
}
inline int C(int n,int m)
{
	return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main()
{
	fac[0]=inv[0]=1;
	for(int i=1;i<=5000;i++) fac[i]=1ll*fac[i-1]*i%mod;
	inv[5000]=qpow(fac[5000],mod-2); 
	for(int i=4999;i>=1;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
	n=read(); 
	s1=s2=n+1;
	for(int i=1;i<n;i++)
	{
		int u=read(), v=read();
		addedge(u,v); addedge(v,u);
	}
	dfs(1);
	if(!(s1^s2)){cout << 1ll*fac[n/2]*fac[n/2]%mod << endl; return 0;}
	else 
	{
		for(int i=st[p1];i;i=vs[i].next)
		{
			if(vs[i].v==fa[p1]) continue;
			bs[++tot]=size[vs[i].v];
		}
		bs[++tot]=n-size[p1]; F[0]=1;
		for(int i=1;i<=tot;i++)
		{
			for(int j=0;j<=n-1;j++) G[j]=F[j];
			for(int j=1;j<=bs[i];j++)
				for(int k=n-1;k>=j;k--) if(F[k-j])
					Add(G[k],1ll*F[k-j]*fac[bs[i]]%mod*inv[bs[i]-j]%mod*C(bs[i],j)%mod);
			for(int j=0;j<=n-1;j++) F[j]=G[j];
		}
		int Ans=fac[n];
		for(int i=1,f=-1;i<=n-1;i++,f*=-1)
			Add(Ans,f*F[i]*fac[n-i]%mod);
		cout << Ans << endl;
	}
	return 0;
}
```