#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<bitset>
#include<map>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long LL;
typedef double db;

int get(){
	char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if (ch=='-'){
		int s=0;
		while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
		return -s;
	}
	int s=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
	return s;
}

const int N = 5005;
const int mo = 1e9+7;

int n;
struct node{
	int x,nxt;
}e[N*2];
int h[N],tot;
int s[N];
int key,v;
LL js[N],inv[N];
LL f[N];

void inse(int x,int y){e[++tot].x=y;e[tot].nxt=h[x];h[x]=tot;}

void dfs(int x){
	s[x]=1;
	int mx=0;
	for(int p=h[x];p;p=e[p].nxt)
	if (!s[e[p].x]){
		dfs(e[p].x);
		s[x]+=s[e[p].x];
		mx=max(mx,s[e[p].x]);
	}
	mx=max(mx,n-s[x]);
	if (!key||mx<v){
		v=mx;
		key=x;
	}
}

int a[N],k;
LL A[N],B[N];

LL calc(int n,int m){return js[n]*inv[m]%mo*inv[n-m]%mo;}

LL add(LL x,LL y){return x+y>=mo?x+y-mo:x+y;}

int main(){
	n=get();
	fo(i,2,n){
		int x=get(),y=get();
		inse(x,y),inse(y,x);
	}
	dfs(1);
	if (v==n/2&&n%2==0){
		LL tmp=1;
		fo(i,2,v)tmp=tmp*i%mo;
		printf("%lld\n",tmp*tmp%mo);
		return 0;
	}
	js[0]=1;
	fo(i,1,n)js[i]=js[i-1]*i%mo;
	inv[0]=inv[1]=1;
	fo(i,2,n)inv[i]=1ll*(mo-mo/i)*inv[mo%i]%mo;
	fo(i,2,n)inv[i]=inv[i]*inv[i-1]%mo;
	k=0;
	if (s[key]<n)a[k=1]=n-s[key];
	for(int p=h[key];p;p=e[p].nxt)
	if (s[e[p].x]<s[key])a[++k]=s[e[p].x];
	s[++k]=1;
	f[0]=1;
	int pre=0;
	fo(i,1,k){
		fo(x,0,pre)A[x]=f[x];
		fo(x,0,a[i])B[x]=calc(a[i],x)*js[a[i]]%mo*inv[a[i]-x]%mo;
		fo(x,0,pre+a[i])f[x]=0;
		fo(x,0,pre)
			fo(y,0,a[i])f[x+y]=add(f[x+y],A[x]*B[y]%mo);
		pre+=a[i];
	}
	fo(i,0,n)f[i]=f[i]*js[n-i]%mo;
	LL ans=0;
	fo(i,0,n)
	if (i&1)ans=(ans+mo-f[i])%mo;else ans=add(ans,f[i]);
	printf("%lld\n",ans);
	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<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<bitset>
#include<map>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long LL;
typedef double db;

int get(){
	char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if (ch=='-'){
		int s=0;
		while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
		return -s;
	}
	int s=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
	return s;
}

const int N = 5005;
const int mo = 1e9+7;

int n;
struct node{
	int x,nxt;
}e[N*2];
int h[N],tot;
int s[N];
int key,v;
LL js[N],inv[N];
LL f[N];

void inse(int x,int y){e[++tot].x=y;e[tot].nxt=h[x];h[x]=tot;}

void dfs(int x){
	s[x]=1;
	int mx=0;
	for(int p=h[x];p;p=e[p].nxt)
	if (!s[e[p].x]){
		dfs(e[p].x);
		s[x]+=s[e[p].x];
		mx=max(mx,s[e[p].x]);
	}
	mx=max(mx,n-s[x]);
	if (!key||mx<v){
		v=mx;
		key=x;
	}
}

int a[N],k;
LL A[N],B[N];

LL calc(int n,int m){return js[n]*inv[m]%mo*inv[n-m]%mo;}

LL add(LL x,LL y){return x+y>=mo?x+y-mo:x+y;}

int main(){
	n=get();
	fo(i,2,n){
		int x=get(),y=get();
		inse(x,y),inse(y,x);
	}
	dfs(1);
	if (v==n/2&&n%2==0){
		LL tmp=1;
		fo(i,2,v)tmp=tmp*i%mo;
		printf("%lld\n",tmp*tmp%mo);
		return 0;
	}
	js[0]=1;
	fo(i,1,n)js[i]=js[i-1]*i%mo;
	inv[0]=inv[1]=1;
	fo(i,2,n)inv[i]=1ll*(mo-mo/i)*inv[mo%i]%mo;
	fo(i,2,n)inv[i]=inv[i]*inv[i-1]%mo;
	k=0;
	if (s[key]<n)a[k=1]=n-s[key];
	for(int p=h[key];p;p=e[p].nxt)
	if (s[e[p].x]<s[key])a[++k]=s[e[p].x];
	s[++k]=1;
	f[0]=1;
	int pre=0;
	fo(i,1,k){
		fo(x,0,pre)A[x]=f[x];
		fo(x,0,a[i])B[x]=calc(a[i],x)*js[a[i]]%mo*inv[a[i]-x]%mo;
		fo(x,0,pre+a[i])f[x]=0;
		fo(x,0,pre)
			fo(y,0,a[i])f[x+y]=add(f[x+y],A[x]*B[y]%mo);
		pre+=a[i];
	}
	fo(i,0,n)f[i]=f[i]*js[n-i]%mo;
	LL ans=0;
	fo(i,0,n)
	if (i&1)ans=(ans+mo-f[i])%mo;else ans=add(ans,f[i]);
	printf("%lld\n",ans);
	return 0;
}
```