#include<iostream>
#include<cstdio>
#define MN 5000
#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;
}
int n,head[MN+5],cnt=0,flag,rt,mn=1e9,ans,size[MN+5],mx[MN+5],p[MN+5],inv[MN+5],f[MN+5],g[MN+5];
struct edge{int to,next;}e[MN*2+5];
inline void ins(int f,int t)
{
	e[++cnt]=(edge){t,head[f]};head[f]=cnt;
	e[++cnt]=(edge){f,head[t]};head[t]=cnt;	
}
void dfs(int x,int fa)
{
	size[x]=1;mx[x]=0;
	for(int i=head[x];i;i=e[i].next)
		if(e[i].to!=fa)
		{
			dfs(e[i].to,x);
			size[x]+=size[e[i].to];mx[x]=max(mx[x],size[e[i].to]);
			if(size[e[i].to]*2==n) flag=1;	
		}
	if(max(n-size[x],mx[x])<mn) mn=max(n-size[x],mx[x]),rt=x;
}
inline int C(int n,int m){return 1LL*p[n]*inv[m]%mod*inv[n-m]%mod;}
inline void R(int&x,int y){x+=y;x>=mod?x-=mod:0;}
int main()
{
	n=read();p[0]=p[1]=inv[0]=inv[1]=f[0]=1;
	for(int i=2;i<=n;++i) p[i]=1LL*p[i-1]*i%mod,inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
	for(int i=2;i<=n;++i) inv[i]=1LL*inv[i-1]*inv[i]%mod; 
	for(int i=1;i<n;++i) ins(read(),read());
	dfs(1,0);if(flag) return 0*printf("%d",1LL*p[n/2]*p[n/2]%mod);
	for(int i=head[rt];i;i=e[i].next)
	{
		int sz=size[e[i].to]>size[rt]?n-size[rt]:size[e[i].to];
		for(int j=0;j<=n;++j) if(f[j])
			for(int k=0;k<=sz;++k)
				R(g[j+k],1LL*f[j]*C(sz,k)%mod*C(sz,k)%mod*p[k]%mod);
		for(int j=0;j<=n;++j) f[j]=g[j],g[j]=0;
	}
	for(int i=0;i<=n;++i) R(ans,1LL*f[i]*((i&1)?mod-1:1)%mod*p[n-i]%mod); 
	cout<<ans;
	return 0;
}


### Prompt

Generate 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<iostream>
#include<cstdio>
#define MN 5000
#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;
}
int n,head[MN+5],cnt=0,flag,rt,mn=1e9,ans,size[MN+5],mx[MN+5],p[MN+5],inv[MN+5],f[MN+5],g[MN+5];
struct edge{int to,next;}e[MN*2+5];
inline void ins(int f,int t)
{
	e[++cnt]=(edge){t,head[f]};head[f]=cnt;
	e[++cnt]=(edge){f,head[t]};head[t]=cnt;	
}
void dfs(int x,int fa)
{
	size[x]=1;mx[x]=0;
	for(int i=head[x];i;i=e[i].next)
		if(e[i].to!=fa)
		{
			dfs(e[i].to,x);
			size[x]+=size[e[i].to];mx[x]=max(mx[x],size[e[i].to]);
			if(size[e[i].to]*2==n) flag=1;	
		}
	if(max(n-size[x],mx[x])<mn) mn=max(n-size[x],mx[x]),rt=x;
}
inline int C(int n,int m){return 1LL*p[n]*inv[m]%mod*inv[n-m]%mod;}
inline void R(int&x,int y){x+=y;x>=mod?x-=mod:0;}
int main()
{
	n=read();p[0]=p[1]=inv[0]=inv[1]=f[0]=1;
	for(int i=2;i<=n;++i) p[i]=1LL*p[i-1]*i%mod,inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
	for(int i=2;i<=n;++i) inv[i]=1LL*inv[i-1]*inv[i]%mod; 
	for(int i=1;i<n;++i) ins(read(),read());
	dfs(1,0);if(flag) return 0*printf("%d",1LL*p[n/2]*p[n/2]%mod);
	for(int i=head[rt];i;i=e[i].next)
	{
		int sz=size[e[i].to]>size[rt]?n-size[rt]:size[e[i].to];
		for(int j=0;j<=n;++j) if(f[j])
			for(int k=0;k<=sz;++k)
				R(g[j+k],1LL*f[j]*C(sz,k)%mod*C(sz,k)%mod*p[k]%mod);
		for(int j=0;j<=n;++j) f[j]=g[j],g[j]=0;
	}
	for(int i=0;i<=n;++i) R(ans,1LL*f[i]*((i&1)?mod-1:1)%mod*p[n-i]%mod); 
	cout<<ans;
	return 0;
}


```