#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>

#define pb push_back
#define mp make_pair

using namespace std;

template<typename T>inline void upmin(T &x,T y) { y<x?x=y:0; }
template<typename T>inline void upmax(T &x,T y) { x<y?x=y:0; }

typedef unsigned int u32;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double lod;
typedef pair<int,int> PR;
typedef vector<int> VI;

const lod pi=acos(-1);
const int oo=1<<30;
const LL OO=1e18;

const int N=5010;
const int mod=1e9+7;

int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}

VI e[N];
int root,siz[N],fac[N],n;
int f[N][N],C[N][N],v[N],fa[N];
inline void dfs(int k) {
	siz[k]=1;int mx=0;
	for (int t:e[k])
		if (t!=fa[k]) {
			fa[t]=k;
			dfs(t);
			siz[k]+=siz[t];
			mx=max(mx,siz[t]);
		}
	mx=max(mx,n-siz[k]);
	if (mx*2<n) root=k;
}
int main()
{
	int i,j,k,a,b,w,ans,m=0;n=gi();
	for (i=1;i<n;i++) {
		a=gi(),b=gi();
		e[a].pb(b),e[b].pb(a);
	}
	for (i=fac[0]=1;i<=n;i++) fac[i]=1LL*fac[i-1]*i%mod;
	dfs(1);
	if (root) {
		for (i=0;i<=n;i++)
			for (j=C[i][0]=1;j<=i;j++)
				C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
		for (int t:e[root])
			v[++m]=fa[root]==t?n-siz[root]:siz[t];
		f[0][1]=1;
		for (i=1;i<=m;i++)
			for (j=1;w=f[i-1][j];j++)
				for (k=0;k<=v[i];k++)
					f[i][j+v[i]-k]=(f[i][j+v[i]-k]+(k&1?-1LL:1LL)*w*C[v[i]][k]%mod*C[v[i]][k]%mod*fac[k])%mod;
		for (i=1,ans=0;i<=n;i++)
			ans=(ans+1LL*f[m][i]*fac[i])%mod;
	} else ans=1LL*fac[n/2]*fac[n/2]%mod;
	cout<<(ans+mod)%mod<<endl;
	return 0;
}

### 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<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>

#define pb push_back
#define mp make_pair

using namespace std;

template<typename T>inline void upmin(T &x,T y) { y<x?x=y:0; }
template<typename T>inline void upmax(T &x,T y) { x<y?x=y:0; }

typedef unsigned int u32;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double lod;
typedef pair<int,int> PR;
typedef vector<int> VI;

const lod pi=acos(-1);
const int oo=1<<30;
const LL OO=1e18;

const int N=5010;
const int mod=1e9+7;

int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}

VI e[N];
int root,siz[N],fac[N],n;
int f[N][N],C[N][N],v[N],fa[N];
inline void dfs(int k) {
	siz[k]=1;int mx=0;
	for (int t:e[k])
		if (t!=fa[k]) {
			fa[t]=k;
			dfs(t);
			siz[k]+=siz[t];
			mx=max(mx,siz[t]);
		}
	mx=max(mx,n-siz[k]);
	if (mx*2<n) root=k;
}
int main()
{
	int i,j,k,a,b,w,ans,m=0;n=gi();
	for (i=1;i<n;i++) {
		a=gi(),b=gi();
		e[a].pb(b),e[b].pb(a);
	}
	for (i=fac[0]=1;i<=n;i++) fac[i]=1LL*fac[i-1]*i%mod;
	dfs(1);
	if (root) {
		for (i=0;i<=n;i++)
			for (j=C[i][0]=1;j<=i;j++)
				C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
		for (int t:e[root])
			v[++m]=fa[root]==t?n-siz[root]:siz[t];
		f[0][1]=1;
		for (i=1;i<=m;i++)
			for (j=1;w=f[i-1][j];j++)
				for (k=0;k<=v[i];k++)
					f[i][j+v[i]-k]=(f[i][j+v[i]-k]+(k&1?-1LL:1LL)*w*C[v[i]][k]%mod*C[v[i]][k]%mod*fac[k])%mod;
		for (i=1,ans=0;i<=n;i++)
			ans=(ans+1LL*f[m][i]*fac[i])%mod;
	} else ans=1LL*fac[n/2]*fac[n/2]%mod;
	cout<<(ans+mod)%mod<<endl;
	return 0;
}

```