#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
const int MO=1e9+7;
LL fac[5010],ANS,inv[5555],f[5010][5010],ans;
int nedge,siz[500010],x,y,n,ts,tmp[5555],root,cnt,mx[500010],too[500010],hed[500010],nxt[500010];
LL pw(LL x,LL y){
	LL t=1;
	for (;y;y>>=1){
		if (y&1) t=t*x%MO;
		x=x*x%MO;
	}
	return t;
}
LL C(int x,int y){
	return fac[x]*inv[y]%MO*inv[x-y]%MO;
}
void ae(int x,int y){
	nxt[++nedge]=hed[x];
	hed[x]=nedge;
	too[nedge]=y;
}
void dfs(int x,int l){
	siz[x]=1;
	for (int i=hed[x];i;i=nxt[i]){
		int y=too[i];
		if (y==l) continue;
		dfs(y,x);
		mx[x]=max(mx[x],siz[y]);
		siz[x]+=siz[y];
	}
	mx[x]=max(mx[x],n-siz[x]);
}
int main(){
	scanf("%d",&n);
	fac[0]=1;
	FOR(i,1,n) fac[i]=fac[i-1]*i%MO;
	inv[n]=pw(fac[n],MO-2);
	FORD(i,n-1,0) inv[i]=inv[i+1]*(i+1)%MO;
	FOR(i,2,n){
		scanf("%d%d",&x,&y);
		ae(x,y),ae(y,x);
	}
	dfs(1,0);
	FOR(i,1,n)
		if (mx[i]<=n/2) root=i,++cnt;
	if (cnt==2) return cout<<fac[n/2]*fac[n/2]%MO<<endl,0;
	dfs(root,0);
	for (int i=hed[root];i;i=nxt[i]){
		int y=too[i];
		tmp[++ts]=siz[y];
	}
	tmp[++ts]=1;
	f[0][0]=1;
	FOR(i,0,ts-1)
		FOR(j,0,n)
			if (f[i][j]){
				FOR(k,0,tmp[i+1])
					(f[i+1][j+k]+=f[i][j]*C(tmp[i+1],k)%MO*C(tmp[i+1],k)%MO*fac[k])%=MO;
			}
	FOR(i,0,n)
		if (i&1) (ans-=f[ts][i]*fac[n-i])%=MO;
		else (ans+=f[ts][i]*fac[n-i])%=MO;
	FOR(i,0,n)
		if (i&1) (ANS-=f[ts-1][i]*fac[n-1-i])%=MO;
		else (ANS+=f[ts-1][i]*fac[n-1-i])%=MO;
	cout<<((ans+ANS)%MO+MO)%MO<<endl;
	return 0;
}

### 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<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
const int MO=1e9+7;
LL fac[5010],ANS,inv[5555],f[5010][5010],ans;
int nedge,siz[500010],x,y,n,ts,tmp[5555],root,cnt,mx[500010],too[500010],hed[500010],nxt[500010];
LL pw(LL x,LL y){
	LL t=1;
	for (;y;y>>=1){
		if (y&1) t=t*x%MO;
		x=x*x%MO;
	}
	return t;
}
LL C(int x,int y){
	return fac[x]*inv[y]%MO*inv[x-y]%MO;
}
void ae(int x,int y){
	nxt[++nedge]=hed[x];
	hed[x]=nedge;
	too[nedge]=y;
}
void dfs(int x,int l){
	siz[x]=1;
	for (int i=hed[x];i;i=nxt[i]){
		int y=too[i];
		if (y==l) continue;
		dfs(y,x);
		mx[x]=max(mx[x],siz[y]);
		siz[x]+=siz[y];
	}
	mx[x]=max(mx[x],n-siz[x]);
}
int main(){
	scanf("%d",&n);
	fac[0]=1;
	FOR(i,1,n) fac[i]=fac[i-1]*i%MO;
	inv[n]=pw(fac[n],MO-2);
	FORD(i,n-1,0) inv[i]=inv[i+1]*(i+1)%MO;
	FOR(i,2,n){
		scanf("%d%d",&x,&y);
		ae(x,y),ae(y,x);
	}
	dfs(1,0);
	FOR(i,1,n)
		if (mx[i]<=n/2) root=i,++cnt;
	if (cnt==2) return cout<<fac[n/2]*fac[n/2]%MO<<endl,0;
	dfs(root,0);
	for (int i=hed[root];i;i=nxt[i]){
		int y=too[i];
		tmp[++ts]=siz[y];
	}
	tmp[++ts]=1;
	f[0][0]=1;
	FOR(i,0,ts-1)
		FOR(j,0,n)
			if (f[i][j]){
				FOR(k,0,tmp[i+1])
					(f[i+1][j+k]+=f[i][j]*C(tmp[i+1],k)%MO*C(tmp[i+1],k)%MO*fac[k])%=MO;
			}
	FOR(i,0,n)
		if (i&1) (ans-=f[ts][i]*fac[n-i])%=MO;
		else (ans+=f[ts][i]*fac[n-i])%=MO;
	FOR(i,0,n)
		if (i&1) (ANS-=f[ts-1][i]*fac[n-1-i])%=MO;
		else (ANS+=f[ts-1][i]*fac[n-1-i])%=MO;
	cout<<((ans+ANS)%MO+MO)%MO<<endl;
	return 0;
}

```