#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma target("avx")
#define ll long long
#define mod 1000000007ll
#define Mod 8223300057563100000ll
using namespace std;
int head[5005],nxt[10005],v[10005],tot=0,n;
int sz[5005],maxn[5005],p[5005],cnt=0,nsz=0;
ll fac[5005],inv[5005],f2[5005],i2[5005],dp[5005],ans=0;
inline void add(int a,int b)
{tot++;nxt[tot]=head[a];head[a]=tot;v[tot]=b;}
inline int max(int a,int b)
{return a>b?a:b;}
void dfs(int pos,int f)
{sz[pos]=1;
for (int i=head[pos];i;i=nxt[i])
{if (v[i]==f) continue;
dfs(v[i],pos);
sz[pos]+=sz[v[i]];
maxn[pos]=max(maxn[pos],sz[v[i]]);
}
maxn[pos]=max(maxn[pos],n-sz[pos]);
}
inline ll cal(int a,int b)
{return (((f2[a]*i2[a-b])%mod)*inv[b])%mod;}
inline ll qpow(ll a,ll b)
{ll res=1,tp=a;
while (b)
{if (b&1ll) res=res*tp%mod;
tp=tp*tp%mod;b>>=1ll;
}
return res;
}
inline void add(int sz)
{int i,j;
for (i=nsz;i>=0;i--)
{for (j=sz;j>=1;j--)
{dp[i+j]+=dp[i]*cal(sz,j);
if (dp[i+j]>Mod) dp[i+j]%=mod;
}
}
nsz+=sz;
for (i=0;i<=nsz;i++) 
{if (dp[i]>=mod) 
{dp[i]%=mod;}
}
}
int main (){
	int i,a,b,msz=233333,num=0,pos;
	scanf ("%d",&n);
	fac[0]=1ll;
	for (i=1;i<=n;i++) fac[i]=fac[i-1]*((ll)(i))%mod;
	inv[n]=qpow(fac[n],mod-2);
	for (i=n-1;i>=0;i--) inv[i]=inv[i+1]*((ll)(i+1))%mod;
	for (i=0;i<=n;i++)
	{f2[i]=fac[i]*fac[i]%mod;
	i2[i]=inv[i]*inv[i]%mod;
	}
	for (i=1;i<n;i++)
	{scanf ("%d%d",&a,&b);
	add(a,b);add(b,a);
	}
	dfs(1,0);
	for (i=1;i<=n;i++)
	{msz=min(msz,maxn[i]);}
	for (i=1;i<=n;i++)
	{if (maxn[i]==msz)
	{pos=i;num++;}
	}
	if (num==2) {printf ("%lld\n",(fac[n/2]*fac[n/2])%mod);return 0;}
	for (i=head[pos];i;i=nxt[i])
	{if (sz[v[i]]>sz[pos]) continue;
	p[++cnt]=sz[v[i]];
	}
	dp[0]=1;
	p[++cnt]=n-sz[pos];
	sort(p+1,p+cnt+1);
	for (i=1;i<=cnt;i++) add(p[i]);
	for (i=0;i<=n;i++)
	{if (i&1) {ans-=dp[i]*fac[n-i];}
	else {ans+=dp[i]*fac[n-i];}
	ans%=mod;
	}
	if (ans<0) ans+=mod;
	printf ("%lld\n",ans);
	return 0;
}
### Prompt

Your challenge is to write 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 <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma target("avx")
#define ll long long
#define mod 1000000007ll
#define Mod 8223300057563100000ll
using namespace std;
int head[5005],nxt[10005],v[10005],tot=0,n;
int sz[5005],maxn[5005],p[5005],cnt=0,nsz=0;
ll fac[5005],inv[5005],f2[5005],i2[5005],dp[5005],ans=0;
inline void add(int a,int b)
{tot++;nxt[tot]=head[a];head[a]=tot;v[tot]=b;}
inline int max(int a,int b)
{return a>b?a:b;}
void dfs(int pos,int f)
{sz[pos]=1;
for (int i=head[pos];i;i=nxt[i])
{if (v[i]==f) continue;
dfs(v[i],pos);
sz[pos]+=sz[v[i]];
maxn[pos]=max(maxn[pos],sz[v[i]]);
}
maxn[pos]=max(maxn[pos],n-sz[pos]);
}
inline ll cal(int a,int b)
{return (((f2[a]*i2[a-b])%mod)*inv[b])%mod;}
inline ll qpow(ll a,ll b)
{ll res=1,tp=a;
while (b)
{if (b&1ll) res=res*tp%mod;
tp=tp*tp%mod;b>>=1ll;
}
return res;
}
inline void add(int sz)
{int i,j;
for (i=nsz;i>=0;i--)
{for (j=sz;j>=1;j--)
{dp[i+j]+=dp[i]*cal(sz,j);
if (dp[i+j]>Mod) dp[i+j]%=mod;
}
}
nsz+=sz;
for (i=0;i<=nsz;i++) 
{if (dp[i]>=mod) 
{dp[i]%=mod;}
}
}
int main (){
	int i,a,b,msz=233333,num=0,pos;
	scanf ("%d",&n);
	fac[0]=1ll;
	for (i=1;i<=n;i++) fac[i]=fac[i-1]*((ll)(i))%mod;
	inv[n]=qpow(fac[n],mod-2);
	for (i=n-1;i>=0;i--) inv[i]=inv[i+1]*((ll)(i+1))%mod;
	for (i=0;i<=n;i++)
	{f2[i]=fac[i]*fac[i]%mod;
	i2[i]=inv[i]*inv[i]%mod;
	}
	for (i=1;i<n;i++)
	{scanf ("%d%d",&a,&b);
	add(a,b);add(b,a);
	}
	dfs(1,0);
	for (i=1;i<=n;i++)
	{msz=min(msz,maxn[i]);}
	for (i=1;i<=n;i++)
	{if (maxn[i]==msz)
	{pos=i;num++;}
	}
	if (num==2) {printf ("%lld\n",(fac[n/2]*fac[n/2])%mod);return 0;}
	for (i=head[pos];i;i=nxt[i])
	{if (sz[v[i]]>sz[pos]) continue;
	p[++cnt]=sz[v[i]];
	}
	dp[0]=1;
	p[++cnt]=n-sz[pos];
	sort(p+1,p+cnt+1);
	for (i=1;i<=cnt;i++) add(p[i]);
	for (i=0;i<=n;i++)
	{if (i&1) {ans-=dp[i]*fac[n-i];}
	else {ans+=dp[i]*fac[n-i];}
	ans%=mod;
	}
	if (ans<0) ans+=mod;
	printf ("%lld\n",ans);
	return 0;
}
```