#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<unordered_map>
#include<array>
#include<map>
#include<bitset>
#include<iomanip>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define RE return 0
//ios::sync_with_stdio(false);
//std::cin.tie(0);
//<< setprecision(20)
const int mod=1e9+7;
const llint big=1e15+100;
const long double pai=3.141592653589793238462643383279502884197;
const long double ena=2.71828182845904523536;
const long double eps=1e-7;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
template <class T> void soun(T& ar)
{sort(ar.begin(),ar.end());ar.erase(unique(ar.begin(),ar.end()),ar.end());}
vector<vector<int>> hen;
vector<int>zyu;//重心からの数
int n,endflag=0;
int make_tree(int ter,int oya){
	vector<int> are;
	int kos=1,flag=1;
	for(auto it:hen[ter]){
		if(it==oya){continue;}
		int a=make_tree(it,ter);
		are.pub(a);
		kos+=a;
		if(a*2>n){flag=0;}
	}
	if(kos*2<n){flag=0;}
	if(kos*2==n){endflag=1;}
	if(flag==1){
		are.pub(n-kos);
		zyu=are;
	}
	return kos;
}
int main(void){
	int i,j;cin>>n;
	hen.res(n);
	vector<llint>fra(n+1);fra[0]=1;
	vector<llint>gya(n+1);
	for(i=0;i<n;i++){fra[i+1]=(fra[i]*(i+1))%mod;}
	llint gen=fra[n];gya[n]=1;
	for(int bi=0;bi<30;bi++){
		if(((mod-2)&(1<<bi))!=0){gya[n]*=gen;gya[n]%=mod;}
		gen=gen*gen;
		gen%=mod;
	}
	for(i=n-1;i>=0;i--){gya[i]=(gya[i+1]*(i+1))%mod;}
	for(i=0;i<n-1;i++){
		int a,b;cin>>a>>b;a--;b--;
		hen[a].pub(b);
		hen[b].pub(a);
	}
	make_tree(0,-1);
	if(endflag==1){cout<<(fra[n/2]*fra[n/2]%mod)<<endl;RE;}
	vector<llint>dp(n+1);
	dp[0]=1;
	for(auto it:zyu){
		vector<llint>ddp(n+1);
		for(i=0;i<=n;i++){
			for(j=0;j<=it;j++){
				if(i+j<0||i+j>n){continue;}
				ddp[i+j]+=((((dp[i]*fra[it])%mod)*((fra[it]*gya[j])%mod))%mod*(gya[it-j]*gya[it-j]%mod))%mod;
			}
		}
		for(i=0;i<=n;i++){dp[i]=ddp[i]%mod;}
	}
	llint ans=0;
	for(i=0;i<=n;i++){
		if(i%2==0){ans+=dp[i]*fra[n-i];}
		else{ans-=dp[i]*fra[n-i];}
		ans%=mod;
	}
	if(ans<0){ans+=mod;}
	cout<<ans<<endl;
	RE;
}
### Prompt

Your challenge is to write 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<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<unordered_map>
#include<array>
#include<map>
#include<bitset>
#include<iomanip>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define RE return 0
//ios::sync_with_stdio(false);
//std::cin.tie(0);
//<< setprecision(20)
const int mod=1e9+7;
const llint big=1e15+100;
const long double pai=3.141592653589793238462643383279502884197;
const long double ena=2.71828182845904523536;
const long double eps=1e-7;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
template <class T> void soun(T& ar)
{sort(ar.begin(),ar.end());ar.erase(unique(ar.begin(),ar.end()),ar.end());}
vector<vector<int>> hen;
vector<int>zyu;//重心からの数
int n,endflag=0;
int make_tree(int ter,int oya){
	vector<int> are;
	int kos=1,flag=1;
	for(auto it:hen[ter]){
		if(it==oya){continue;}
		int a=make_tree(it,ter);
		are.pub(a);
		kos+=a;
		if(a*2>n){flag=0;}
	}
	if(kos*2<n){flag=0;}
	if(kos*2==n){endflag=1;}
	if(flag==1){
		are.pub(n-kos);
		zyu=are;
	}
	return kos;
}
int main(void){
	int i,j;cin>>n;
	hen.res(n);
	vector<llint>fra(n+1);fra[0]=1;
	vector<llint>gya(n+1);
	for(i=0;i<n;i++){fra[i+1]=(fra[i]*(i+1))%mod;}
	llint gen=fra[n];gya[n]=1;
	for(int bi=0;bi<30;bi++){
		if(((mod-2)&(1<<bi))!=0){gya[n]*=gen;gya[n]%=mod;}
		gen=gen*gen;
		gen%=mod;
	}
	for(i=n-1;i>=0;i--){gya[i]=(gya[i+1]*(i+1))%mod;}
	for(i=0;i<n-1;i++){
		int a,b;cin>>a>>b;a--;b--;
		hen[a].pub(b);
		hen[b].pub(a);
	}
	make_tree(0,-1);
	if(endflag==1){cout<<(fra[n/2]*fra[n/2]%mod)<<endl;RE;}
	vector<llint>dp(n+1);
	dp[0]=1;
	for(auto it:zyu){
		vector<llint>ddp(n+1);
		for(i=0;i<=n;i++){
			for(j=0;j<=it;j++){
				if(i+j<0||i+j>n){continue;}
				ddp[i+j]+=((((dp[i]*fra[it])%mod)*((fra[it]*gya[j])%mod))%mod*(gya[it-j]*gya[it-j]%mod))%mod;
			}
		}
		for(i=0;i<=n;i++){dp[i]=ddp[i]%mod;}
	}
	llint ans=0;
	for(i=0;i<=n;i++){
		if(i%2==0){ans+=dp[i]*fra[n-i];}
		else{ans-=dp[i]*fra[n-i];}
		ans%=mod;
	}
	if(ans<0){ans+=mod;}
	cout<<ans<<endl;
	RE;
}
```