#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll tmp=998244353;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

const int M=5005;
ll F[M];

void Init(){
	F[0]=1;
	for(int i=1;i<M;i++) F[i]=F[i-1]*i%mod;
}

ll n,C[M][M];
vl a,s;
vvi g;

void dfs(int v,int p){
	s[v]=1;
	for(auto u:g[v]) if(u!=p){
		dfs(u,v);
		s[v]+=s[u];
	}
}

int main(){
	Init();
	C[0][0]++;
	for(int i=0;i<M-1;i++) for(int j=0;j<=i;j++){
		(C[i+1][j]+=C[i][j])%=mod;
		(C[i+1][j+1]+=C[i][j])%=mod;
	}
	cin>>n;
	g=vvi(n);
	s=vl(n);
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		u--;v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	int G=-1;
	for(int i=0;i<n;i++){
		dfs(i,-1);
		bool B=1;
		for(auto u:g[i]) if(s[u]*2>n) B=0;
		if(B){
			if(G<0) G=i;
			else{
				cout<<F[n-s[G]]*F[s[G]]%mod<<endl;
				return 0;
			}
		}
	}
	dfs(G,-1);
	for(auto u:g[G]) a.push_back(s[u]);
	vl dp(n+1);
	dp[0]++;
	int t=0;
	for(auto i:a){
		vl DP(n+1);
		for(int j=0;j<=t;j++) for(int k=0;k<=min(n-j,i);k++) (DP[j+k]+=dp[j]*C[i][k]%mod*C[i][k]%mod*F[k])%=mod;
		t+=i;
		dp=DP;
	}
	ll res=0;
	for(int i=0;i<=n;i++) (res+=dp[i]*F[n-i]%mod*(i%2==0?1:mod-1))%=mod;
	cout<<res<<endl;
}
### 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 <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll tmp=998244353;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

const int M=5005;
ll F[M];

void Init(){
	F[0]=1;
	for(int i=1;i<M;i++) F[i]=F[i-1]*i%mod;
}

ll n,C[M][M];
vl a,s;
vvi g;

void dfs(int v,int p){
	s[v]=1;
	for(auto u:g[v]) if(u!=p){
		dfs(u,v);
		s[v]+=s[u];
	}
}

int main(){
	Init();
	C[0][0]++;
	for(int i=0;i<M-1;i++) for(int j=0;j<=i;j++){
		(C[i+1][j]+=C[i][j])%=mod;
		(C[i+1][j+1]+=C[i][j])%=mod;
	}
	cin>>n;
	g=vvi(n);
	s=vl(n);
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		u--;v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	int G=-1;
	for(int i=0;i<n;i++){
		dfs(i,-1);
		bool B=1;
		for(auto u:g[i]) if(s[u]*2>n) B=0;
		if(B){
			if(G<0) G=i;
			else{
				cout<<F[n-s[G]]*F[s[G]]%mod<<endl;
				return 0;
			}
		}
	}
	dfs(G,-1);
	for(auto u:g[G]) a.push_back(s[u]);
	vl dp(n+1);
	dp[0]++;
	int t=0;
	for(auto i:a){
		vl DP(n+1);
		for(int j=0;j<=t;j++) for(int k=0;k<=min(n-j,i);k++) (DP[j+k]+=dp[j]*C[i][k]%mod*C[i][k]%mod*F[k])%=mod;
		t+=i;
		dp=DP;
	}
	ll res=0;
	for(int i=0;i<=n;i++) (res+=dp[i]*F[n-i]%mod*(i%2==0?1:mod-1))%=mod;
	cout<<res<<endl;
}
```