#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#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;
}
inline void write(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
inline void pr1(int x){write(x),putchar(' ');}
inline void pr2(int x){write(x),puts("");}
struct node
{
	int x,y,next;
}a[10010];int len,last[5010];
inline void ins(int x,int y)
{
	len++;
	a[len].x=x;a[len].y=y;
	a[len].next=last[x];last[x]=len;
}
int n,f[2][5010],tot[5010],ans,p,cnt;
inline void dfs(int x,int fa)
{
	tot[x]=1;int mx=0;
	for(int k=last[x];k;k=a[k].next)
	{
		int y=a[k].y;
		if(y==fa)continue;
		dfs(y,x);
		tot[x]+=tot[y];
		mx=max(mx,tot[y]);
	}mx=max(mx,n-tot[x]);
	if(mx<ans)ans=mx,p=x,cnt=1;
	else if(mx==ans)cnt++;
}
inline void update(int x,int fa)
{
	tot[x]=1;
	for(int k=last[x];k;k=a[k].next)
	{
		int y=a[k].y;
		if(y==fa)continue;
		update(y,x);
		tot[x]+=tot[y];
	}
}
int fac[5010],inv[5010];
inline int C(int m,int n){return 1LL*fac[m]*inv[n]%mod*inv[m-n]%mod;}
inline int A(int m,int n){return 1LL*fac[m]*inv[m-n]%mod;}
inline int power(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1)ans=1LL*ans*a%mod;
		a=1LL*a*a%mod;
		b>>=1;
	}return ans;
}
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    fac[0]=1;
    for(int i=1;i<=5000;i++)fac[i]=1LL*fac[i-1]*i%mod;inv[5000]=power(fac[5000],mod-2);
    for(int i=5000;i>=1;i--)inv[i-1]=1LL*inv[i]*i%mod;
    n=read();
	for(int i=1;i<n;i++)
	{
		int x=read(),y=read();
		ins(x,y),ins(y,x);
	}ans=n;
	dfs(1,0);
	if(cnt==2)pr2(1LL*fac[n/2]*fac[n/2]%mod);
	else
	{
		update(p,0);int now=1;
		f[0][0]=1;int he=0;
		for(int k=last[p];k;k=a[k].next)
		{
			int y=a[k].y;he^=1;
			memset(f[he],0,sizeof(f[he]));
			for(int i=now;i>=0;i--)
			{
				for(int j=0;j<=tot[y];j++)(f[he][i+j]+=1LL*f[he^1][i]*C(tot[y],j)%mod*A(tot[y],j)%mod)%=mod;
			}now+=tot[y];
		}
		for(int i=0;i<=now;i++)f[he][i]=1LL*f[he][i]*fac[now-i]%mod;
		int ans=0,id=1;
		for(int i=0;i<=now;i++)(ans+=(f[he][i]*id+mod)%mod)%=mod,id=-id;	
		pr2(ans);
	}
    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<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#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;
}
inline void write(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
inline void pr1(int x){write(x),putchar(' ');}
inline void pr2(int x){write(x),puts("");}
struct node
{
	int x,y,next;
}a[10010];int len,last[5010];
inline void ins(int x,int y)
{
	len++;
	a[len].x=x;a[len].y=y;
	a[len].next=last[x];last[x]=len;
}
int n,f[2][5010],tot[5010],ans,p,cnt;
inline void dfs(int x,int fa)
{
	tot[x]=1;int mx=0;
	for(int k=last[x];k;k=a[k].next)
	{
		int y=a[k].y;
		if(y==fa)continue;
		dfs(y,x);
		tot[x]+=tot[y];
		mx=max(mx,tot[y]);
	}mx=max(mx,n-tot[x]);
	if(mx<ans)ans=mx,p=x,cnt=1;
	else if(mx==ans)cnt++;
}
inline void update(int x,int fa)
{
	tot[x]=1;
	for(int k=last[x];k;k=a[k].next)
	{
		int y=a[k].y;
		if(y==fa)continue;
		update(y,x);
		tot[x]+=tot[y];
	}
}
int fac[5010],inv[5010];
inline int C(int m,int n){return 1LL*fac[m]*inv[n]%mod*inv[m-n]%mod;}
inline int A(int m,int n){return 1LL*fac[m]*inv[m-n]%mod;}
inline int power(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1)ans=1LL*ans*a%mod;
		a=1LL*a*a%mod;
		b>>=1;
	}return ans;
}
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    fac[0]=1;
    for(int i=1;i<=5000;i++)fac[i]=1LL*fac[i-1]*i%mod;inv[5000]=power(fac[5000],mod-2);
    for(int i=5000;i>=1;i--)inv[i-1]=1LL*inv[i]*i%mod;
    n=read();
	for(int i=1;i<n;i++)
	{
		int x=read(),y=read();
		ins(x,y),ins(y,x);
	}ans=n;
	dfs(1,0);
	if(cnt==2)pr2(1LL*fac[n/2]*fac[n/2]%mod);
	else
	{
		update(p,0);int now=1;
		f[0][0]=1;int he=0;
		for(int k=last[p];k;k=a[k].next)
		{
			int y=a[k].y;he^=1;
			memset(f[he],0,sizeof(f[he]));
			for(int i=now;i>=0;i--)
			{
				for(int j=0;j<=tot[y];j++)(f[he][i+j]+=1LL*f[he^1][i]*C(tot[y],j)%mod*A(tot[y],j)%mod)%=mod;
			}now+=tot[y];
		}
		for(int i=0;i<=now;i++)f[he][i]=1LL*f[he][i]*fac[now-i]%mod;
		int ans=0,id=1;
		for(int i=0;i<=now;i++)(ans+=(f[he][i]*id+mod)%mod)%=mod,id=-id;	
		pr2(ans);
	}
    return 0;
}
```