#include <bits/stdc++.h>
using namespace std;

using ll=int64_t;
#define int ll

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define ALL(x) x.begin(),x.end()
#define REACH cerr<<"reached line "<<__LINE__<<endl
#define DMP(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
#define ZERO(x) memset(x,0,sizeof(x))

using pi=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"[";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"]";
	return os;
}

int read(){
	int i;
	scanf("%" SCNd64,&i);
	return i;
}

void printSpace(){
	printf(" ");
}

void printEoln(){
	printf("\n");
}

void print(int x,int suc=1){
	printf("%" PRId64,x);
	if(suc==1)
		printEoln();
	if(suc==2)
		printSpace();
}

string readString(){
	static char buf[3341919];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341919];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

template<class T,class U>
void chmax(T& a,U b){
	if(a<b)
		a=b;
}

template<class T,class U>
void chmin(T& a,U b){
	if(a>b)
		a=b;
}

template<class T>
T Sq(const T& t){
	return t*t;
}

const int Nmax=5140;
const int inf=LLONG_MAX/3;
int n;
vi g[Nmax];
int FindCentroid(int v,int p){
	int res=1,s=0;
	for(auto to:g[v])if(to!=p){
		int fc=FindCentroid(to,v);
		if(fc<=0)return fc;
		chmax(s,fc);
		res+=fc;
	}
	chmax(s,n-res);
	if(s*2<=n)return -v;
	return res;
}

int SubSize(int v,int p){
	int res=1;
	for(auto to:g[v])if(to!=p)
		res+=SubSize(to,v);
	return res;
}

const int mod=1000000007;
template<class T,class U>
void add(T& a,U b){
	a=((ll)a+b)%mod;
}

template<class T,class U>
void sub(T& a,U b){
	a=((ll)a-b%mod+mod)%mod;
}

template<class T,class U>
void mult(T& a,U b){
	a=((ll)a*b)%mod;
}

ll modPow(ll a,ll p){
	ll s=1;
	REP(i,30){
		if((p>>i)&1)
			mult(s,a);
		mult(a,a);
	}
	return s;
}

ll modInv(ll a){
	return modPow(a,mod-2);
}

int fact[Nmax],factInv[Nmax];
void Init(){
	fact[0]=1;
	FOR(i,1,Nmax){
		fact[i]=i;
		mult(fact[i],fact[i-1]);
	}
	factInv[Nmax-1]=modInv(fact[Nmax-1]);
	for(int i=Nmax-2;i>=0;i--){
		factInv[i]=factInv[i+1];
		mult(factInv[i],i+1);
	}
}

int Choose(int a,int b){
	return fact[a]*factInv[a-b]%mod*factInv[b]%mod;
}

int dp[2][Nmax];
int buf[Nmax];

int Solve(vi ss){
	//cerr<<ss<<endl;
	int cur=0,nx=1,maxS=0;
	ZERO(dp[cur]);
	dp[cur][0]=1;
	for(auto s:ss){
		ZERO(dp[nx]);
		REP(i,s+1)
			buf[i]=Choose(s,i)*fact[s]%mod*factInv[s-i]%mod;
		REP(i,maxS+1)REP(j,s+1)
			add(dp[nx][i+j],dp[cur][i]*buf[j]);
		maxS+=s;
		swap(cur,nx);
	}
	int res=0;
	REP(i,maxS+1)
		(i%2?sub<int,int>:add<int,int>)(res,dp[cur][i]*fact[maxS-i]);
	return res;
}

signed main(){
	Init();
	n=read();
	REP(i,n-1){
		int x=read()-1,y=read()-1;
		g[x].PB(y);
		g[y].PB(x);
	}
	int root=-FindCentroid(0,-1);
	vi ss;
	for(auto to:g[root])
		ss.PB(SubSize(to,root));
	ss.PB(1);
	int ans=0;
	add(ans,Solve(ss));
	ss.pop_back();
	add(ans,Solve(ss));
	cout<<ans<<endl;
}
### Prompt

Generate 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 <bits/stdc++.h>
using namespace std;

using ll=int64_t;
#define int ll

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define ALL(x) x.begin(),x.end()
#define REACH cerr<<"reached line "<<__LINE__<<endl
#define DMP(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
#define ZERO(x) memset(x,0,sizeof(x))

using pi=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"[";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"]";
	return os;
}

int read(){
	int i;
	scanf("%" SCNd64,&i);
	return i;
}

void printSpace(){
	printf(" ");
}

void printEoln(){
	printf("\n");
}

void print(int x,int suc=1){
	printf("%" PRId64,x);
	if(suc==1)
		printEoln();
	if(suc==2)
		printSpace();
}

string readString(){
	static char buf[3341919];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341919];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

template<class T,class U>
void chmax(T& a,U b){
	if(a<b)
		a=b;
}

template<class T,class U>
void chmin(T& a,U b){
	if(a>b)
		a=b;
}

template<class T>
T Sq(const T& t){
	return t*t;
}

const int Nmax=5140;
const int inf=LLONG_MAX/3;
int n;
vi g[Nmax];
int FindCentroid(int v,int p){
	int res=1,s=0;
	for(auto to:g[v])if(to!=p){
		int fc=FindCentroid(to,v);
		if(fc<=0)return fc;
		chmax(s,fc);
		res+=fc;
	}
	chmax(s,n-res);
	if(s*2<=n)return -v;
	return res;
}

int SubSize(int v,int p){
	int res=1;
	for(auto to:g[v])if(to!=p)
		res+=SubSize(to,v);
	return res;
}

const int mod=1000000007;
template<class T,class U>
void add(T& a,U b){
	a=((ll)a+b)%mod;
}

template<class T,class U>
void sub(T& a,U b){
	a=((ll)a-b%mod+mod)%mod;
}

template<class T,class U>
void mult(T& a,U b){
	a=((ll)a*b)%mod;
}

ll modPow(ll a,ll p){
	ll s=1;
	REP(i,30){
		if((p>>i)&1)
			mult(s,a);
		mult(a,a);
	}
	return s;
}

ll modInv(ll a){
	return modPow(a,mod-2);
}

int fact[Nmax],factInv[Nmax];
void Init(){
	fact[0]=1;
	FOR(i,1,Nmax){
		fact[i]=i;
		mult(fact[i],fact[i-1]);
	}
	factInv[Nmax-1]=modInv(fact[Nmax-1]);
	for(int i=Nmax-2;i>=0;i--){
		factInv[i]=factInv[i+1];
		mult(factInv[i],i+1);
	}
}

int Choose(int a,int b){
	return fact[a]*factInv[a-b]%mod*factInv[b]%mod;
}

int dp[2][Nmax];
int buf[Nmax];

int Solve(vi ss){
	//cerr<<ss<<endl;
	int cur=0,nx=1,maxS=0;
	ZERO(dp[cur]);
	dp[cur][0]=1;
	for(auto s:ss){
		ZERO(dp[nx]);
		REP(i,s+1)
			buf[i]=Choose(s,i)*fact[s]%mod*factInv[s-i]%mod;
		REP(i,maxS+1)REP(j,s+1)
			add(dp[nx][i+j],dp[cur][i]*buf[j]);
		maxS+=s;
		swap(cur,nx);
	}
	int res=0;
	REP(i,maxS+1)
		(i%2?sub<int,int>:add<int,int>)(res,dp[cur][i]*fact[maxS-i]);
	return res;
}

signed main(){
	Init();
	n=read();
	REP(i,n-1){
		int x=read()-1,y=read()-1;
		g[x].PB(y);
		g[y].PB(x);
	}
	int root=-FindCentroid(0,-1);
	vi ss;
	for(auto to:g[root])
		ss.PB(SubSize(to,root));
	ss.PB(1);
	int ans=0;
	add(ans,Solve(ss));
	ss.pop_back();
	add(ans,Solve(ss));
	cout<<ans<<endl;
}
```