#include<bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int MAXN=1E4+10;
const int P=1E9+7;

template<typename T1,typename T2>
	void Inc(T1 &a,T2 b){a+=b;if(a>=P) a-=P;}

template<typename T1,typename T2>
	void Dec(T1 &a,T2 b){a-=b;if(a<0) a+=P;}

template<typename T1,typename T2>
	T1 Add(T1 a,T2 b){a+=b;return a>=P?a-P:a;}

template<typename T1,typename T2>
	T1 Sub(T1 a,T2 b){a-=b;return a<0?a+P:a;}

ll ksm(ll a,ll b)
{
	ll ret=1;
	for(;b;b>>=1,(a*=a)%=P)
		if(b&1)
			(ret*=a)%=P;
	return ret;
}

int n,siz[MAXN],rt,mxrt;
vector<int> T[MAXN];
ll fac[MAXN],ifac[MAXN],f[2][MAXN];

ll C(int n,int m){return fac[n]*ifac[n-m]%P*ifac[m]%P;}

ll A(int n,int m){return fac[n]*ifac[n-m]%P;}

void find_rt(int x,int fa)
{
	siz[x]=1;
	int mx=0;
	for(int v:T[x])
		if(v!=fa)
		{
			find_rt(v,x);
			siz[x]+=siz[v];
			mx=max(mx,siz[v]);
		}
	mx=max(mx,n-siz[x]);
	if(mx<mxrt)
		mxrt=mx,rt=x;
}

int main()
{
	scanf("%d",&n);
	for(int i=1,u,v;i<n;i++)
		scanf("%d%d",&u,&v),
		T[u].push_back(v),
		T[v].push_back(u);
	fac[0]=ifac[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=fac[i-1]*i%P;
	ifac[n]=ksm(fac[n],P-2);
	for(int i=n-1;i;i--)
		ifac[i]=ifac[i+1]*(i+1)%P;
	mxrt=1<<30;
	find_rt(1,0);
	if(~n&1&&mxrt==n/2)
		return printf("%lld\n",fac[n/2]*fac[n/2]%P),0;
	find_rt(rt,0);
	int lst=0;
	f[lst][0]=1;
	for(int v:T[rt])
	{
		memcpy(f[!lst],f[lst],sizeof f[!lst]);
		for(int i=0;i<=n;i++)
			for(int j=1;j<=siz[v]&&i+j<=n;j++)
				Inc(f[!lst][i+j],f[lst][i]*A(siz[v],j)%P*C(siz[v],j)%P);
		lst^=1;
	}
	ll Ans=0;
	for(int i=0;i<=n;i++)
	{
		if(i&1)
			Dec(Ans,f[lst][i]*fac[n-i]%P);
		else
			Inc(Ans,f[lst][i]*fac[n-i]%P);
	}
	printf("%lld\n",Ans);
}

### Prompt

Your task is to create 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>

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int MAXN=1E4+10;
const int P=1E9+7;

template<typename T1,typename T2>
	void Inc(T1 &a,T2 b){a+=b;if(a>=P) a-=P;}

template<typename T1,typename T2>
	void Dec(T1 &a,T2 b){a-=b;if(a<0) a+=P;}

template<typename T1,typename T2>
	T1 Add(T1 a,T2 b){a+=b;return a>=P?a-P:a;}

template<typename T1,typename T2>
	T1 Sub(T1 a,T2 b){a-=b;return a<0?a+P:a;}

ll ksm(ll a,ll b)
{
	ll ret=1;
	for(;b;b>>=1,(a*=a)%=P)
		if(b&1)
			(ret*=a)%=P;
	return ret;
}

int n,siz[MAXN],rt,mxrt;
vector<int> T[MAXN];
ll fac[MAXN],ifac[MAXN],f[2][MAXN];

ll C(int n,int m){return fac[n]*ifac[n-m]%P*ifac[m]%P;}

ll A(int n,int m){return fac[n]*ifac[n-m]%P;}

void find_rt(int x,int fa)
{
	siz[x]=1;
	int mx=0;
	for(int v:T[x])
		if(v!=fa)
		{
			find_rt(v,x);
			siz[x]+=siz[v];
			mx=max(mx,siz[v]);
		}
	mx=max(mx,n-siz[x]);
	if(mx<mxrt)
		mxrt=mx,rt=x;
}

int main()
{
	scanf("%d",&n);
	for(int i=1,u,v;i<n;i++)
		scanf("%d%d",&u,&v),
		T[u].push_back(v),
		T[v].push_back(u);
	fac[0]=ifac[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=fac[i-1]*i%P;
	ifac[n]=ksm(fac[n],P-2);
	for(int i=n-1;i;i--)
		ifac[i]=ifac[i+1]*(i+1)%P;
	mxrt=1<<30;
	find_rt(1,0);
	if(~n&1&&mxrt==n/2)
		return printf("%lld\n",fac[n/2]*fac[n/2]%P),0;
	find_rt(rt,0);
	int lst=0;
	f[lst][0]=1;
	for(int v:T[rt])
	{
		memcpy(f[!lst],f[lst],sizeof f[!lst]);
		for(int i=0;i<=n;i++)
			for(int j=1;j<=siz[v]&&i+j<=n;j++)
				Inc(f[!lst][i+j],f[lst][i]*A(siz[v],j)%P*C(siz[v],j)%P);
		lst^=1;
	}
	ll Ans=0;
	for(int i=0;i<=n;i++)
	{
		if(i&1)
			Dec(Ans,f[lst][i]*fac[n-i]%P);
		else
			Inc(Ans,f[lst][i]*fac[n-i]%P);
	}
	printf("%lld\n",Ans);
}

```