#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline int read()
{
	int f=1,x=0;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;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
const int mod=1e9+7;
const int MAXN=5005;
int pow_mod(int a,int b)
{
	int ret=1;
	for(;b;b>>=1,a=1LL*a*a%mod)if(b&1)ret=1LL*ret*a%mod;
	return ret;
}
struct edge{int x,y,next;}a[2*MAXN];int len,last[MAXN];
void ins(int x,int y){len++;a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len;}
int tot[MAXN];
int pre[2*MAXN],inv[2*MAXN];
int C(int n,int m){return 1LL*pre[n]*inv[m]%mod*inv[n-m]%mod;}
void ad(int &x,int y){x+=y;if(x>=mod)x-=mod;}
int n,mx[MAXN];
void init(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)init(y,x),tot[x]+=tot[y],mx[x]=max(mx[x],tot[y]);
	}
	mx[x]=max(mx[x],n-tot[x]);
}
int rt,f[MAXN][MAXN],temp[MAXN];
void dp(int x,int fa)
{
	tot[x]=1;if(x==rt)f[x][1]=1;
	for(int k=last[x];k;k=a[k].next)
	{
		int y=a[k].y;
		if(y!=fa)
		{
			dp(y,x);
			if(x==rt)
			{
				for(int i=0;i<=tot[x];i++)for(int j=0;j<=tot[y];j++)
					ad(temp[i+j],1LL*f[x][i]*f[y][j]%mod);
				for(int i=0;i<=tot[x]+tot[y];i++)f[x][i]=temp[i],temp[i]=0;
			}
			tot[x]+=tot[y];
		}
	}
	if(fa==rt)
		for(int i=0;i<=tot[x];i++)f[x][i]=1LL*((tot[x]-i)&1?(mod-1):1)*pre[tot[x]]%mod*inv[i]%mod*pre[tot[x]]%mod*inv[i]%mod*inv[tot[x]-i]%mod;
}
int main()
{
	pre[0]=1;for(int i=1;i<2*MAXN;i++)pre[i]=1LL*pre[i-1]*i%mod;
	inv[2*MAXN-1]=pow_mod(pre[2*MAXN-1],mod-2);
	for(int i=2*MAXN-2;i>=0;i--)inv[i]=1LL*inv[i+1]*(i+1)%mod;
	n=read();
	for(int i=1;i<n;i++)
	{
		int x=read(),y=read();
		ins(x,y);ins(y,x);
	}
	init(1,0);
	int cnt=0;
	for(int i=1;i<=n;i++)if(2*mx[i]<=n)++cnt,rt=i;
	if(cnt==2)return pr2(1LL*pre[n/2]*pre[n/2]%mod),0;
	dp(rt,0);int ans=0;
	for(int i=0;i<=n;i++)ad(ans,1LL*f[rt][i]*pre[i]%mod);
	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<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline int read()
{
	int f=1,x=0;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;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
const int mod=1e9+7;
const int MAXN=5005;
int pow_mod(int a,int b)
{
	int ret=1;
	for(;b;b>>=1,a=1LL*a*a%mod)if(b&1)ret=1LL*ret*a%mod;
	return ret;
}
struct edge{int x,y,next;}a[2*MAXN];int len,last[MAXN];
void ins(int x,int y){len++;a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len;}
int tot[MAXN];
int pre[2*MAXN],inv[2*MAXN];
int C(int n,int m){return 1LL*pre[n]*inv[m]%mod*inv[n-m]%mod;}
void ad(int &x,int y){x+=y;if(x>=mod)x-=mod;}
int n,mx[MAXN];
void init(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)init(y,x),tot[x]+=tot[y],mx[x]=max(mx[x],tot[y]);
	}
	mx[x]=max(mx[x],n-tot[x]);
}
int rt,f[MAXN][MAXN],temp[MAXN];
void dp(int x,int fa)
{
	tot[x]=1;if(x==rt)f[x][1]=1;
	for(int k=last[x];k;k=a[k].next)
	{
		int y=a[k].y;
		if(y!=fa)
		{
			dp(y,x);
			if(x==rt)
			{
				for(int i=0;i<=tot[x];i++)for(int j=0;j<=tot[y];j++)
					ad(temp[i+j],1LL*f[x][i]*f[y][j]%mod);
				for(int i=0;i<=tot[x]+tot[y];i++)f[x][i]=temp[i],temp[i]=0;
			}
			tot[x]+=tot[y];
		}
	}
	if(fa==rt)
		for(int i=0;i<=tot[x];i++)f[x][i]=1LL*((tot[x]-i)&1?(mod-1):1)*pre[tot[x]]%mod*inv[i]%mod*pre[tot[x]]%mod*inv[i]%mod*inv[tot[x]-i]%mod;
}
int main()
{
	pre[0]=1;for(int i=1;i<2*MAXN;i++)pre[i]=1LL*pre[i-1]*i%mod;
	inv[2*MAXN-1]=pow_mod(pre[2*MAXN-1],mod-2);
	for(int i=2*MAXN-2;i>=0;i--)inv[i]=1LL*inv[i+1]*(i+1)%mod;
	n=read();
	for(int i=1;i<n;i++)
	{
		int x=read(),y=read();
		ins(x,y);ins(y,x);
	}
	init(1,0);
	int cnt=0;
	for(int i=1;i<=n;i++)if(2*mx[i]<=n)++cnt,rt=i;
	if(cnt==2)return pr2(1LL*pre[n/2]*pre[n/2]%mod),0;
	dp(rt,0);int ans=0;
	for(int i=0;i<=n;i++)ad(ans,1LL*f[rt][i]*pre[i]%mod);
	pr2(ans);
	return 0;
}

```