#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(a,b,c) for (int a=b;a<=c;a++)
#define per(a,b,c) for (int a=b;a>=c;a--)
#define go(u) for (int o=ft[u],v;v=E[o].t;o=E[o].n)
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef double dob;
typedef pair<int,int> par;
const int N=5010,P=1000000007;
struct edge{int t,n;}E[N<<1];
int n,rt,ft[N],s[N],key[N],tot;
LL f[N],g[N],s1[N],s2[N],inv[N];
void add(int x,int y){
	E[++tot]=(edge){y,ft[x]},ft[x]=tot;
}
void dfs1(int u,int f=0){
	go(u) if (v!=f) dfs1(v,u),s[u]+=s[v];
	++s[u];
}
void dfs2(int u,int f=0){
	key[u]=n-s[u];
	go(u) if (v!=f) dfs2(v,u),key[u]=max(key[u],s[v]);
	if (key[u]<key[rt]) rt=u;
}
LL C(int n,int m){return s1[n]*s2[m]%P*s2[n-m]%P;}
void preset(){
	int lim=5000;
	inv[1]=s1[0]=s2[0]=1;
	rep(i,2,lim) inv[i]=inv[P%i]*(P-P/i)%P;
	rep(i,1,lim) s1[i]=s1[i-1]*i%P,s2[i]=s2[i-1]*inv[i]%P;
}
void upd(LL &x,LL y){x=(x+y)%P;}
int main(){
	preset();
	scanf("%d",&n);
	rep(i,2,n){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	dfs1(1);
	key[0]=n+10;
	dfs2(1);
	if (n%2==0&&key[rt]==n/2){
		printf("%lld\n",s1[n/2]*s1[n/2]%P);
		return 0;
	}
	f[0]=1;
	memset(s,0,sizeof(s));
	dfs1(rt);
	go(rt){
		int sum=s[v];
		memset(g,0,sizeof(g));
		rep(i,0,n){
			LL fx=f[i];
			rep(j,0,sum) upd(g[i+j],fx*C(sum,j)%P*C(sum,j)%P*s1[j]%P);
		}
		swap(f,g);
	}
	LL ans=0;
	rep(i,0,n) upd(ans,f[i]*(i&1?-1:1)*s1[n-i]%P);
	ans=(ans+P)%P;
	printf("%lld\n",ans);
	return 0;
}

### Prompt

Please formulate 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<cstdio>
#include<cstring>
#include<algorithm>
#define rep(a,b,c) for (int a=b;a<=c;a++)
#define per(a,b,c) for (int a=b;a>=c;a--)
#define go(u) for (int o=ft[u],v;v=E[o].t;o=E[o].n)
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef double dob;
typedef pair<int,int> par;
const int N=5010,P=1000000007;
struct edge{int t,n;}E[N<<1];
int n,rt,ft[N],s[N],key[N],tot;
LL f[N],g[N],s1[N],s2[N],inv[N];
void add(int x,int y){
	E[++tot]=(edge){y,ft[x]},ft[x]=tot;
}
void dfs1(int u,int f=0){
	go(u) if (v!=f) dfs1(v,u),s[u]+=s[v];
	++s[u];
}
void dfs2(int u,int f=0){
	key[u]=n-s[u];
	go(u) if (v!=f) dfs2(v,u),key[u]=max(key[u],s[v]);
	if (key[u]<key[rt]) rt=u;
}
LL C(int n,int m){return s1[n]*s2[m]%P*s2[n-m]%P;}
void preset(){
	int lim=5000;
	inv[1]=s1[0]=s2[0]=1;
	rep(i,2,lim) inv[i]=inv[P%i]*(P-P/i)%P;
	rep(i,1,lim) s1[i]=s1[i-1]*i%P,s2[i]=s2[i-1]*inv[i]%P;
}
void upd(LL &x,LL y){x=(x+y)%P;}
int main(){
	preset();
	scanf("%d",&n);
	rep(i,2,n){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	dfs1(1);
	key[0]=n+10;
	dfs2(1);
	if (n%2==0&&key[rt]==n/2){
		printf("%lld\n",s1[n/2]*s1[n/2]%P);
		return 0;
	}
	f[0]=1;
	memset(s,0,sizeof(s));
	dfs1(rt);
	go(rt){
		int sum=s[v];
		memset(g,0,sizeof(g));
		rep(i,0,n){
			LL fx=f[i];
			rep(j,0,sum) upd(g[i+j],fx*C(sum,j)%P*C(sum,j)%P*s1[j]%P);
		}
		swap(f,g);
	}
	LL ans=0;
	rep(i,0,n) upd(ans,f[i]*(i&1?-1:1)*s1[n-i]%P);
	ans=(ans+P)%P;
	printf("%lld\n",ans);
	return 0;
}

```