#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
 
#define mod 1000000007
#define FOR(x,to) for(int x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define long long long
inline int rei(){int x;cin>>x;return x;}
inline long rel(){long x;cin>>x;return x;}
inline string res(){string x;cin>>x;return x;}
namespace Fact{
	long f[1000000];
	long rf[1000000];
	long pow(long N,long K){
		if(K == 0){
			return 1;
		}
		else if(K % 2 == 0){
			long t = pow(N,K/2);
			return t*t%mod;
		}
		else{
			return N*pow(N,K-1)%mod;
		}
	}
	void Fact(int N){
		for(int i=0;i<N+1;i++){
			if(i == 0){
				f[i] = 1;
			}
			else{
				f[i] = (f[i-1]*i)%mod;
			}
		}
		for(int i=N;i>=0;i--){
			if(i == N){
				rf[i] = pow(f[N],mod-2);
			}
			else{
				rf[i] = rf[i+1]*(i+1)%mod;
			}
		}
	}
	long GetFact(int N){
		return f[N];
	}
	long GetPerm(int N,int R){
		return f[N] * rf[N-R] % mod;
	}
	long GetConv(int N,int R){
		return ((f[N]*rf[R])%mod*rf[N-R])%mod;
	}
	long GetRev(int N){
		if(N == 0){
			return 1;
		}
		else{
			return rf[N] * f[N-1] % mod;
		}
	}
}
//-------------------------------------------------------
int ChildNum[5000];
vector<int> G[5000];
long DP[5000*5001];
long DP2[5000*5001];
void GetChildNum(int v,int f){
	int ans = 1;
	for(int i=0;i<G[v].size();i++){
		int t = G[v][i];
		if(t != f){
			GetChildNum(t,v);
			ans += ChildNum[t];
		}
	}
	ChildNum[v] = ans;
}
int GetCenter(int v,int f,int N){
	for(int i=0;i<G[v].size();i++){
		int t = G[v][i];
		if(t != f){
			if(ChildNum[t] >= N){
				return GetCenter(t,v,N);
			}
		}
	}
	return v;
}
void Calc(){
	int N = rei();
	Fact::Fact(100000);
	for(int i=0;i<N-1;i++){
		int x = rei()-1;
		int y = rei()-1;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	GetChildNum(0,-1);
	int Center = GetCenter(0,-1,(N+1)/2);
	if(ChildNum[Center] * 2 == N){
		cout << Fact::GetFact(N/2) * Fact::GetFact(N/2) % mod << endl;
		return;
	}
	GetChildNum(Center,-1);
	for(int i=0;i<G[Center].size();i++){
		int t = G[Center][i];
		int c = ChildNum[t];
		for(int j=0;j<=c;j++){
			DP[t*5001+j] = Fact::GetConv(c,j) * Fact::GetPerm(c,j) % mod;
		}
	}
	DP2[0] = 1;
	int ch = 0;
	for(int i=0;i<G[Center].size();i++){
		int t = G[Center][i];
		int c = ChildNum[t];
		for(int k=0;k<=ch;k++){
			DP2[i*5001+k] %= mod;
			for(int j=c;j>=0;j--){
				DP2[i*5001+5001+j+k] += DP2[i*5001+k] * DP[t*5001+j] % mod;
			}
		}
		ch += c;
	}
	long ans = 0;
	for(int i=0;i<=N-1;i++){
		if(i % 2 == 0){
			ans += DP2[G[Center].size()*5001+i] % mod * Fact::GetFact(N-i) % mod;
		}
		else{
			ans += mod - DP2[G[Center].size()*5001+i] % mod * Fact::GetFact(N-i) % mod;
		}
	}
	ans %= mod;
	cout << ans << endl;
}
int main(int argc,char** argv){
	ios::sync_with_stdio(false), cin.tie(0);
	cout.tie(0); Calc(); return 0;
}
### Prompt

Create a solution in cpp for 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 <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
 
#define mod 1000000007
#define FOR(x,to) for(int x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define long long long
inline int rei(){int x;cin>>x;return x;}
inline long rel(){long x;cin>>x;return x;}
inline string res(){string x;cin>>x;return x;}
namespace Fact{
	long f[1000000];
	long rf[1000000];
	long pow(long N,long K){
		if(K == 0){
			return 1;
		}
		else if(K % 2 == 0){
			long t = pow(N,K/2);
			return t*t%mod;
		}
		else{
			return N*pow(N,K-1)%mod;
		}
	}
	void Fact(int N){
		for(int i=0;i<N+1;i++){
			if(i == 0){
				f[i] = 1;
			}
			else{
				f[i] = (f[i-1]*i)%mod;
			}
		}
		for(int i=N;i>=0;i--){
			if(i == N){
				rf[i] = pow(f[N],mod-2);
			}
			else{
				rf[i] = rf[i+1]*(i+1)%mod;
			}
		}
	}
	long GetFact(int N){
		return f[N];
	}
	long GetPerm(int N,int R){
		return f[N] * rf[N-R] % mod;
	}
	long GetConv(int N,int R){
		return ((f[N]*rf[R])%mod*rf[N-R])%mod;
	}
	long GetRev(int N){
		if(N == 0){
			return 1;
		}
		else{
			return rf[N] * f[N-1] % mod;
		}
	}
}
//-------------------------------------------------------
int ChildNum[5000];
vector<int> G[5000];
long DP[5000*5001];
long DP2[5000*5001];
void GetChildNum(int v,int f){
	int ans = 1;
	for(int i=0;i<G[v].size();i++){
		int t = G[v][i];
		if(t != f){
			GetChildNum(t,v);
			ans += ChildNum[t];
		}
	}
	ChildNum[v] = ans;
}
int GetCenter(int v,int f,int N){
	for(int i=0;i<G[v].size();i++){
		int t = G[v][i];
		if(t != f){
			if(ChildNum[t] >= N){
				return GetCenter(t,v,N);
			}
		}
	}
	return v;
}
void Calc(){
	int N = rei();
	Fact::Fact(100000);
	for(int i=0;i<N-1;i++){
		int x = rei()-1;
		int y = rei()-1;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	GetChildNum(0,-1);
	int Center = GetCenter(0,-1,(N+1)/2);
	if(ChildNum[Center] * 2 == N){
		cout << Fact::GetFact(N/2) * Fact::GetFact(N/2) % mod << endl;
		return;
	}
	GetChildNum(Center,-1);
	for(int i=0;i<G[Center].size();i++){
		int t = G[Center][i];
		int c = ChildNum[t];
		for(int j=0;j<=c;j++){
			DP[t*5001+j] = Fact::GetConv(c,j) * Fact::GetPerm(c,j) % mod;
		}
	}
	DP2[0] = 1;
	int ch = 0;
	for(int i=0;i<G[Center].size();i++){
		int t = G[Center][i];
		int c = ChildNum[t];
		for(int k=0;k<=ch;k++){
			DP2[i*5001+k] %= mod;
			for(int j=c;j>=0;j--){
				DP2[i*5001+5001+j+k] += DP2[i*5001+k] * DP[t*5001+j] % mod;
			}
		}
		ch += c;
	}
	long ans = 0;
	for(int i=0;i<=N-1;i++){
		if(i % 2 == 0){
			ans += DP2[G[Center].size()*5001+i] % mod * Fact::GetFact(N-i) % mod;
		}
		else{
			ans += mod - DP2[G[Center].size()*5001+i] % mod * Fact::GetFact(N-i) % mod;
		}
	}
	ans %= mod;
	cout << ans << endl;
}
int main(int argc,char** argv){
	ios::sync_with_stdio(false), cin.tie(0);
	cout.tie(0); Calc(); return 0;
}
```