#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 5005
const int inf=1e9,mod=1e9+7;

int n,m,tot,root;
int now[maxn],pre[maxn*2],son[maxn*2],mx[maxn],size[maxn],fac[maxn],inv[maxn];
int f[maxn][maxn];

inline int read(){
	int x=0,f=1; char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*f;
}

inline void print(int x){
	if (x<0){putchar('-'); x=-x;}
	if (x>=10) print(x/10);
	putchar(x%10+'0');
}

void add(int a,int b){son[++tot]=b,pre[tot]=now[a],now[a]=tot;}
void link(int a,int b){add(a,b),add(b,a);}

void find_root(int x,int fa){
	size[x]=1;
	for (int p=now[x];p;p=pre[p])
		if (son[p]!=fa){
			find_root(son[p],x),size[x]+=size[son[p]];
			mx[x]=max(mx[x],size[son[p]]);
		}
	mx[x]=max(mx[x],n-size[x]);
	if (mx[x]<mx[root]) root=x;
}

void dfs(int x,int fa){
	size[x]=1;
	for (int p=now[x];p;p=pre[p])
		if (son[p]!=fa) dfs(son[p],x),size[x]+=size[son[p]];
}

int C(int n,int m){return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;}
int A(int n,int m){return 1ll*fac[n]*inv[n-m]%mod;}

int main(){
	n=read();
	for (int i=1,x,y;i<n;i++) x=read(),y=read(),link(x,y);
	mx[root]=inf,find_root(1,0);
	if ((~n&1)&&mx[root]==(n>>1)){
		int ans=1,pps=n>>1;
		for (int i=2;i<=pps;i++) ans=1ll*ans*i%mod;
		ans=1ll*ans*ans%mod;
		cout<<ans<<endl;
		return 0;
	}
	fac[0]=1; for (int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
	inv[0]=inv[1]=1; for (int i=2;i<=n;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	for (int i=1;i<=n;i++) inv[i]=1ll*inv[i]*inv[i-1]%mod;
	dfs(root,0); f[0][0]=1; int i=1;
	for (int p=now[root];p;p=pre[p],i++){
		int x=son[p];
		for (int j=0;j<=size[x];j++)
			for (int k=0;k+j<n;k++)
				f[i][j+k]=(f[i][j+k]+1ll*f[i-1][k]*C(size[x],j)%mod*A(size[x],j))%mod;
	}
	--i;
	int ans=0;
	for (int x=0;x<n;x++)
		ans=(ans+1ll*(x&1?-1:1)*fac[n-x]*f[i][x])%mod;
	cout<<(ans+mod)%mod<<endl;
	return 0;
}

### Prompt

In cpp, your task is to solve 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<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 5005
const int inf=1e9,mod=1e9+7;

int n,m,tot,root;
int now[maxn],pre[maxn*2],son[maxn*2],mx[maxn],size[maxn],fac[maxn],inv[maxn];
int f[maxn][maxn];

inline int read(){
	int x=0,f=1; char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*f;
}

inline void print(int x){
	if (x<0){putchar('-'); x=-x;}
	if (x>=10) print(x/10);
	putchar(x%10+'0');
}

void add(int a,int b){son[++tot]=b,pre[tot]=now[a],now[a]=tot;}
void link(int a,int b){add(a,b),add(b,a);}

void find_root(int x,int fa){
	size[x]=1;
	for (int p=now[x];p;p=pre[p])
		if (son[p]!=fa){
			find_root(son[p],x),size[x]+=size[son[p]];
			mx[x]=max(mx[x],size[son[p]]);
		}
	mx[x]=max(mx[x],n-size[x]);
	if (mx[x]<mx[root]) root=x;
}

void dfs(int x,int fa){
	size[x]=1;
	for (int p=now[x];p;p=pre[p])
		if (son[p]!=fa) dfs(son[p],x),size[x]+=size[son[p]];
}

int C(int n,int m){return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;}
int A(int n,int m){return 1ll*fac[n]*inv[n-m]%mod;}

int main(){
	n=read();
	for (int i=1,x,y;i<n;i++) x=read(),y=read(),link(x,y);
	mx[root]=inf,find_root(1,0);
	if ((~n&1)&&mx[root]==(n>>1)){
		int ans=1,pps=n>>1;
		for (int i=2;i<=pps;i++) ans=1ll*ans*i%mod;
		ans=1ll*ans*ans%mod;
		cout<<ans<<endl;
		return 0;
	}
	fac[0]=1; for (int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
	inv[0]=inv[1]=1; for (int i=2;i<=n;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	for (int i=1;i<=n;i++) inv[i]=1ll*inv[i]*inv[i-1]%mod;
	dfs(root,0); f[0][0]=1; int i=1;
	for (int p=now[root];p;p=pre[p],i++){
		int x=son[p];
		for (int j=0;j<=size[x];j++)
			for (int k=0;k+j<n;k++)
				f[i][j+k]=(f[i][j+k]+1ll*f[i-1][k]*C(size[x],j)%mod*A(size[x],j))%mod;
	}
	--i;
	int ans=0;
	for (int x=0;x<n;x++)
		ans=(ans+1ll*(x&1?-1:1)*fac[n-x]*f[i][x])%mod;
	cout<<(ans+mod)%mod<<endl;
	return 0;
}

```