#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;

#define pb push_back
#define fr first
#define sc second

const ll M = 1000000007;

ll fac[5002];
void init_fac(int MAX_N = 5000){
	fac[0] = 1;
	for(int i = 1 ; i <= MAX_N ; i ++){
		fac[i] = fac[i-1]*i;
		fac[i] %= M;
	}
}
ll C[5002][5002];
void init_C(int MAX_N = 5000, int MAX_K = 5000){
	C[0][0] = 1;
	for(int i = 0 ; i <= MAX_N ; i ++){
		for(int j = 0 ; j <= i ; j ++){
			C[i][j] %= M;
			C[i+1][j] += C[i][j];
			C[i+1][j+1] += C[i][j];
		}
	}
}

int N;
vector<int> G[5002];
ll ret[5002];

ll dp[2][5002] = {};
ll memo[5002];

int dfs(int v,int p){
	ret[v] = 1;
	
	vector<ll> vec;
	ll cnt = 1;
	for(int i = 0 ; i < G[v].size() ; i ++){
		if(G[v][i] == p)continue;
		vec.pb(dfs(G[v][i],v));
		cnt += vec[vec.size()-1];
	}
	if(p != 0)vec.pb(N-cnt);
	
	sort(vec.begin(),vec.end());
	reverse(vec.begin(),vec.end());
	if(vec[0] > N-vec[0]){
		ret[v] = 1;
	}
	else if(vec[0] == N-vec[0]){
		ret[v] *= fac[N-vec[0]];
		ret[v] %= M;
	}
	else {
		int t = 0 , t_ = 1;
		int sum = 0;
		dp[t][0] = 1;
		for(int i = 0 ; i < vec.size() ; i ++){
			int d = vec[i];
			for(int j = 0 ; j < 5002 ; j ++){
				dp[t_][j] = 0;
			}
			for(int m = 0 ; m <= min(sum,5000-sum) ; m ++){
				for(int k = 0 ; k <= d ; k ++){
					memo[k] = 1;
					memo[k] *= C[m][k];
					memo[k] *= C[d][k]; memo[k] %= M;
					memo[k] *= fac[k]; memo[k] %= M;
				}
				for(int n = max(0,m-d) ; n <= min(sum+d,min(m+d,5000-sum-d)) ; n ++){
					ll X = 0;
					int MIN_K = max(0,m-n);
					int MAX_K = min(m+d-n,min(d,m));
					for(int k = MIN_K ; k <= MAX_K ; ++k){
						int l = m+d-n-k;
						if(l <= k){
							X *= 2;
							if(l == k){
								X += memo[k]*memo[k];
							}
							break;
						}
						/*int l = m+d-n-k;
						if(l < k && MIN_K <= l){}
						else {
							memo[k] *= memo[l];
							memo[k] %= M;
							memo[l] = memo[k];
						}
						X += memo[k];*/
						ll Y = memo[k];
						Y *= memo[l];
						Y %= M;
						X += Y;
					}
					X %= M;
					dp[t_][n] += dp[t][m]*X;
					dp[t_][n] %= M;
				}
			}
			/*for(int n = 0 ; n <= min(sum+d,5000-sum-d) ; n ++){
				for(int m = max(0,n-d) ; m <= min(sum,min(n+d,5000-sum)) ; m ++){
					ll X = 0;
					for(int k = max(0,m-n) ; k <= min(m+d-n,m) ; k ++){
						ll Y = 1;
						Y *= C[m][k]; Y %= M;
						Y *= C[d][k]; Y %= M;
						Y *= fac[k]; Y %= M;
						int l = m+d-n-k;
						Y *= C[m][l]; Y %= M;
						Y *= C[d][l]; Y %= M;
						Y *= fac[l]; Y %= M;
						X += Y;
					}
					X %= M;
					dp[t_][n] += dp[t][m]*X;
					dp[t_][n] %= M;
				}
			}*/
			sum += d;
			swap(t,t_);
		}
		ret[v] = (dp[t][0]+dp[t][1])%M;
	}
	
	return cnt;
}

int main(){
	init_fac();
	init_C();
	
	scanf("%d",&N);
	for(int i = 0 ; i < N-1 ; i ++){
		int x,y;
		scanf("%d%d",&x,&y);
		G[x].pb(y);
		G[y].pb(x);
	}
	
	int root = 1;
	dfs(1,0);
	
	ll RET = 1;
	for(int i = 1 ; i <= N ; i ++){
		RET *= ret[i];
		RET %= M;
	}
	cout << RET << endl;
}


### 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<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;

#define pb push_back
#define fr first
#define sc second

const ll M = 1000000007;

ll fac[5002];
void init_fac(int MAX_N = 5000){
	fac[0] = 1;
	for(int i = 1 ; i <= MAX_N ; i ++){
		fac[i] = fac[i-1]*i;
		fac[i] %= M;
	}
}
ll C[5002][5002];
void init_C(int MAX_N = 5000, int MAX_K = 5000){
	C[0][0] = 1;
	for(int i = 0 ; i <= MAX_N ; i ++){
		for(int j = 0 ; j <= i ; j ++){
			C[i][j] %= M;
			C[i+1][j] += C[i][j];
			C[i+1][j+1] += C[i][j];
		}
	}
}

int N;
vector<int> G[5002];
ll ret[5002];

ll dp[2][5002] = {};
ll memo[5002];

int dfs(int v,int p){
	ret[v] = 1;
	
	vector<ll> vec;
	ll cnt = 1;
	for(int i = 0 ; i < G[v].size() ; i ++){
		if(G[v][i] == p)continue;
		vec.pb(dfs(G[v][i],v));
		cnt += vec[vec.size()-1];
	}
	if(p != 0)vec.pb(N-cnt);
	
	sort(vec.begin(),vec.end());
	reverse(vec.begin(),vec.end());
	if(vec[0] > N-vec[0]){
		ret[v] = 1;
	}
	else if(vec[0] == N-vec[0]){
		ret[v] *= fac[N-vec[0]];
		ret[v] %= M;
	}
	else {
		int t = 0 , t_ = 1;
		int sum = 0;
		dp[t][0] = 1;
		for(int i = 0 ; i < vec.size() ; i ++){
			int d = vec[i];
			for(int j = 0 ; j < 5002 ; j ++){
				dp[t_][j] = 0;
			}
			for(int m = 0 ; m <= min(sum,5000-sum) ; m ++){
				for(int k = 0 ; k <= d ; k ++){
					memo[k] = 1;
					memo[k] *= C[m][k];
					memo[k] *= C[d][k]; memo[k] %= M;
					memo[k] *= fac[k]; memo[k] %= M;
				}
				for(int n = max(0,m-d) ; n <= min(sum+d,min(m+d,5000-sum-d)) ; n ++){
					ll X = 0;
					int MIN_K = max(0,m-n);
					int MAX_K = min(m+d-n,min(d,m));
					for(int k = MIN_K ; k <= MAX_K ; ++k){
						int l = m+d-n-k;
						if(l <= k){
							X *= 2;
							if(l == k){
								X += memo[k]*memo[k];
							}
							break;
						}
						/*int l = m+d-n-k;
						if(l < k && MIN_K <= l){}
						else {
							memo[k] *= memo[l];
							memo[k] %= M;
							memo[l] = memo[k];
						}
						X += memo[k];*/
						ll Y = memo[k];
						Y *= memo[l];
						Y %= M;
						X += Y;
					}
					X %= M;
					dp[t_][n] += dp[t][m]*X;
					dp[t_][n] %= M;
				}
			}
			/*for(int n = 0 ; n <= min(sum+d,5000-sum-d) ; n ++){
				for(int m = max(0,n-d) ; m <= min(sum,min(n+d,5000-sum)) ; m ++){
					ll X = 0;
					for(int k = max(0,m-n) ; k <= min(m+d-n,m) ; k ++){
						ll Y = 1;
						Y *= C[m][k]; Y %= M;
						Y *= C[d][k]; Y %= M;
						Y *= fac[k]; Y %= M;
						int l = m+d-n-k;
						Y *= C[m][l]; Y %= M;
						Y *= C[d][l]; Y %= M;
						Y *= fac[l]; Y %= M;
						X += Y;
					}
					X %= M;
					dp[t_][n] += dp[t][m]*X;
					dp[t_][n] %= M;
				}
			}*/
			sum += d;
			swap(t,t_);
		}
		ret[v] = (dp[t][0]+dp[t][1])%M;
	}
	
	return cnt;
}

int main(){
	init_fac();
	init_C();
	
	scanf("%d",&N);
	for(int i = 0 ; i < N-1 ; i ++){
		int x,y;
		scanf("%d%d",&x,&y);
		G[x].pb(y);
		G[y].pb(x);
	}
	
	int root = 1;
	dfs(1,0);
	
	ll RET = 1;
	for(int i = 1 ; i <= N ; i ++){
		RET *= ret[i];
		RET %= M;
	}
	cout << RET << endl;
}


```