#include<bits/stdc++.h>
using namespace std;
const int N=5010,p=1e9+7;
int inc(int x,int y){x+=y;return x>=p?x-p:x;}
int mul(int x,int y){return (long long)x*y%p;}
int power(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=mul(x,x))
		if (y&1) ans=mul(ans,x);
	return ans;
}
void update(int &x,int v){x+=v;if (x>=p) x-=p;}
vector<int> e[N];
int n,size[N],big[N],root;
void getroot(int x,int fa){
	size[x]=1;
	for (auto v:e[x])
	if (v!=fa){
		getroot(v,x);
		size[x]+=size[v];
		big[x]=max(big[x],size[v]);
	}
	if (size[x]*2>=n&&big[x]*2<=n) root=x;
}
int dp[N],fac[N],ifac[N],K[N],f[2][N],*a=f[0],*b=f[1];
int main()
{
	scanf("%d",&n);
	fac[0]=1;
	for (int i=1;i<=n;i++) fac[i]=mul(fac[i-1],i);
	ifac[n]=power(fac[n],p-2);
	for (int i=n;i;i--) ifac[i-1]=mul(ifac[i],i);
	for (int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	getroot(1,0);
	getroot(root,0);
	a[0]=1;
	int dp_size=1;
	for (auto v:e[root]){
		for (int i=0;i<=dp_size;i++) b[i]=0;
		int s=size[v];
		for (int i=0;i<=dp_size;i++)
		for (int j=0;j<=s;j++){
			int k=mul(fac[s],ifac[s-j]);
			k=mul(mul(k,k),ifac[j]);
			update(b[i+j],mul(a[i],k));
		}
		swap(a,b);
		dp_size+=s;
	}
	int ans=0;
	for (int i=0;i<=n;i++) update(ans,mul(i&1?p-1:1,mul(a[i],fac[n-i])));
	printf("%d\n",ans);
	return 0;
}
### Prompt

Construct a Cpp code solution to the problem outlined:

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;
const int N=5010,p=1e9+7;
int inc(int x,int y){x+=y;return x>=p?x-p:x;}
int mul(int x,int y){return (long long)x*y%p;}
int power(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=mul(x,x))
		if (y&1) ans=mul(ans,x);
	return ans;
}
void update(int &x,int v){x+=v;if (x>=p) x-=p;}
vector<int> e[N];
int n,size[N],big[N],root;
void getroot(int x,int fa){
	size[x]=1;
	for (auto v:e[x])
	if (v!=fa){
		getroot(v,x);
		size[x]+=size[v];
		big[x]=max(big[x],size[v]);
	}
	if (size[x]*2>=n&&big[x]*2<=n) root=x;
}
int dp[N],fac[N],ifac[N],K[N],f[2][N],*a=f[0],*b=f[1];
int main()
{
	scanf("%d",&n);
	fac[0]=1;
	for (int i=1;i<=n;i++) fac[i]=mul(fac[i-1],i);
	ifac[n]=power(fac[n],p-2);
	for (int i=n;i;i--) ifac[i-1]=mul(ifac[i],i);
	for (int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	getroot(1,0);
	getroot(root,0);
	a[0]=1;
	int dp_size=1;
	for (auto v:e[root]){
		for (int i=0;i<=dp_size;i++) b[i]=0;
		int s=size[v];
		for (int i=0;i<=dp_size;i++)
		for (int j=0;j<=s;j++){
			int k=mul(fac[s],ifac[s-j]);
			k=mul(mul(k,k),ifac[j]);
			update(b[i+j],mul(a[i],k));
		}
		swap(a,b);
		dp_size+=s;
	}
	int ans=0;
	for (int i=0;i<=n;i++) update(ans,mul(i&1?p-1:1,mul(a[i],fac[n-i])));
	printf("%d\n",ans);
	return 0;
}
```