#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
#define pb push_back
const int N=5000+5,D=1e9+7;
ll mi(ll x,int y=D-2)
{
	ll ans=1;
	while(y)
	{
		if(y&1)ans=ans*x%D;
		x=x*x%D;y>>=1;
	}
	return ans;
}
int n;
vector<int>lk[N];
int fa[N],sz[N],q[N];
ll jie[N],nijie[N];
ll qa[2][N],*dp=qa[0],*dp0=qa[1];

void bfs(int rt)
{
	int tail=1;
	q[1]=rt;
	fa[rt]=0;
	rep(head,1,tail)
	{
		int x=q[head];
		for(auto y:lk[x])
		if(y!=fa[x])
		{
			fa[y]=x;
			q[++tail]=y;
		}
	}
	rep(x,1,n)sz[x]=1;
	per(head,tail,1)
	{
		int x=q[head];
		sz[fa[x]]+=sz[x];
	}
}

ll C(int n,int m)
{
	return jie[n]*nijie[m]%D*nijie[n-m]%D;
}

int main()
{
	//freopen("1.in","r",stdin);
	cin>>n;
	rep(i,1,n-1)
	{
		int x,y;
		cin>>x>>y;
		lk[x].pb(y);lk[y].pb(x);
	}
	bfs(1);
	int rt=0;
	per(head,n,1)
	{
		int x=q[head];
		if(sz[x]>=(n+1)/2)
		{
			rt=x;
			break;
		}
	}
	bfs(rt);
	jie[0]=1;
	rep(i,1,n)jie[i]=jie[i-1]*i%D;
	nijie[n]=mi(jie[n]);
	per(i,n-1,0)nijie[i]=nijie[i+1]*(i+1)%D;
	int tot=1;
	dp[0]=1;
	for(auto y:lk[rt])
	{
		int nsz=sz[y];
		swap(dp,dp0);
		rep(i,0,tot+nsz)dp[i]=0;
		rep(j,0,nsz)
		{
			ll fj=C(nsz,j)*C(nsz,j)%D*jie[j]%D;
			rep(i,0,tot)(dp[i+j]+=dp0[i]*fj)%=D;
		}
		tot+=nsz;
	}
	ll ans=0;
	rep(i,0,n)
	{
		if(i%2==0)(ans+=dp[i]*jie[n-i])%=D;
		else (ans-=dp[i]*jie[n-i])%=D;
	}
	cout<<(ans+D)%D<<endl;
}
### Prompt

Please provide a cpp coded solution 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>
using namespace std;

typedef long long ll;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
#define pb push_back
const int N=5000+5,D=1e9+7;
ll mi(ll x,int y=D-2)
{
	ll ans=1;
	while(y)
	{
		if(y&1)ans=ans*x%D;
		x=x*x%D;y>>=1;
	}
	return ans;
}
int n;
vector<int>lk[N];
int fa[N],sz[N],q[N];
ll jie[N],nijie[N];
ll qa[2][N],*dp=qa[0],*dp0=qa[1];

void bfs(int rt)
{
	int tail=1;
	q[1]=rt;
	fa[rt]=0;
	rep(head,1,tail)
	{
		int x=q[head];
		for(auto y:lk[x])
		if(y!=fa[x])
		{
			fa[y]=x;
			q[++tail]=y;
		}
	}
	rep(x,1,n)sz[x]=1;
	per(head,tail,1)
	{
		int x=q[head];
		sz[fa[x]]+=sz[x];
	}
}

ll C(int n,int m)
{
	return jie[n]*nijie[m]%D*nijie[n-m]%D;
}

int main()
{
	//freopen("1.in","r",stdin);
	cin>>n;
	rep(i,1,n-1)
	{
		int x,y;
		cin>>x>>y;
		lk[x].pb(y);lk[y].pb(x);
	}
	bfs(1);
	int rt=0;
	per(head,n,1)
	{
		int x=q[head];
		if(sz[x]>=(n+1)/2)
		{
			rt=x;
			break;
		}
	}
	bfs(rt);
	jie[0]=1;
	rep(i,1,n)jie[i]=jie[i-1]*i%D;
	nijie[n]=mi(jie[n]);
	per(i,n-1,0)nijie[i]=nijie[i+1]*(i+1)%D;
	int tot=1;
	dp[0]=1;
	for(auto y:lk[rt])
	{
		int nsz=sz[y];
		swap(dp,dp0);
		rep(i,0,tot+nsz)dp[i]=0;
		rep(j,0,nsz)
		{
			ll fj=C(nsz,j)*C(nsz,j)%D*jie[j]%D;
			rep(i,0,tot)(dp[i+j]+=dp0[i]*fj)%=D;
		}
		tot+=nsz;
	}
	ll ans=0;
	rep(i,0,n)
	{
		if(i%2==0)(ans+=dp[i]*jie[n-i])%=D;
		else (ans-=dp[i]*jie[n-i])%=D;
	}
	cout<<(ans+D)%D<<endl;
}
```