#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>
#include <random>

using namespace std;
typedef long long LL;

const LL M=1e9+7;
const int L=5001;
vector<int> ps[L];
int ww[L];
int N;
LL C[L][L];
LL F[L];
vector<int> cs;
int dfs(int i,int r){
	int s=1;
	bool center=true;
	for(auto p:ps[i]){
		if(p==r)continue;
		int v=dfs(p,i);
		if(v>N/2){
			center=false;
		}
		s+=v;
	}
	ww[i]=s;
	if(N-s>N/2){
		center=false;
	}
	if(center){
		cs.push_back(i);
	}
	//cerr << i << ", " << ww[i] << endl;
	return s;
}
LL dp[L][L];
int main() {
	cin >> N;
	for(int i=1;i<N;i++){
		int x,y;
		cin >> x >> y;
		ps[x].push_back(y);
		ps[y].push_back(x);
	}
	dfs(1,0);
	for(int i=0;i<L;i++){
		C[i][0]=1;
		for(int j=1;j<=i;j++){
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%M;
		}
	}
	F[0]=1;
	for(int i=1;i<L;i++){
		F[i]=F[i-1]*i%M;
	}
	//cerr << cs.size() << endl;
	if(cs.size()==2){
		cout << F[N/2]*F[N/2]%M << endl;
		return 0;
	}
	int c=cs[0];
	for(auto p:ps[c]){
		if(ww[p]>ww[c]){
			ww[p]=N-ww[c];
		}
	}
	dp[0][0]=1;
	int sum=0;
	for(int i=0;i<ps[c].size();i++){
		auto w=ww[ps[c][i]];
		for(int j=0;j<=sum;j++){
			for(int k=0;k<=w;k++){
				dp[i+1][j+k]+=dp[i][j]*C[w][k]%M*C[w][k]%M*F[k]%M;
				dp[i+1][j+k]%=M;
			}
		}
		sum+=w;
	}
	int sg=1;
	LL ret=0;
	for(int i=0;i<=N;i++){
		//cerr << F[N-i] << ", " << dp[ps[c].size()][i] << endl;
		ret+=(M+sg)*F[N-i]%M*dp[ps[c].size()][i]%M;
		ret%=M;
		sg*=-1;
		//cerr << ret << endl;
	}
	cout << ret << endl;

	return 0;
}


### 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 <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>
#include <random>

using namespace std;
typedef long long LL;

const LL M=1e9+7;
const int L=5001;
vector<int> ps[L];
int ww[L];
int N;
LL C[L][L];
LL F[L];
vector<int> cs;
int dfs(int i,int r){
	int s=1;
	bool center=true;
	for(auto p:ps[i]){
		if(p==r)continue;
		int v=dfs(p,i);
		if(v>N/2){
			center=false;
		}
		s+=v;
	}
	ww[i]=s;
	if(N-s>N/2){
		center=false;
	}
	if(center){
		cs.push_back(i);
	}
	//cerr << i << ", " << ww[i] << endl;
	return s;
}
LL dp[L][L];
int main() {
	cin >> N;
	for(int i=1;i<N;i++){
		int x,y;
		cin >> x >> y;
		ps[x].push_back(y);
		ps[y].push_back(x);
	}
	dfs(1,0);
	for(int i=0;i<L;i++){
		C[i][0]=1;
		for(int j=1;j<=i;j++){
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%M;
		}
	}
	F[0]=1;
	for(int i=1;i<L;i++){
		F[i]=F[i-1]*i%M;
	}
	//cerr << cs.size() << endl;
	if(cs.size()==2){
		cout << F[N/2]*F[N/2]%M << endl;
		return 0;
	}
	int c=cs[0];
	for(auto p:ps[c]){
		if(ww[p]>ww[c]){
			ww[p]=N-ww[c];
		}
	}
	dp[0][0]=1;
	int sum=0;
	for(int i=0;i<ps[c].size();i++){
		auto w=ww[ps[c][i]];
		for(int j=0;j<=sum;j++){
			for(int k=0;k<=w;k++){
				dp[i+1][j+k]+=dp[i][j]*C[w][k]%M*C[w][k]%M*F[k]%M;
				dp[i+1][j+k]%=M;
			}
		}
		sum+=w;
	}
	int sg=1;
	LL ret=0;
	for(int i=0;i<=N;i++){
		//cerr << F[N-i] << ", " << dp[ps[c].size()][i] << endl;
		ret+=(M+sg)*F[N-i]%M*dp[ps[c].size()][i]%M;
		ret%=M;
		sg*=-1;
		//cerr << ret << endl;
	}
	cout << ret << endl;

	return 0;
}


```