#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

const int MC = 5010;
const LL mod = 1e9 + 7;
int N;
vector<int> V[MC];
int c[MC],parent[MC];
int g = -1;
LL fct[MC+1];
LL invfct[MC+1];
LL dp[2][MC];

void build(){
	fct[0] = fct[1] = 1;
	repp(i,2,MC+1){
		fct[i] = fct[i-1] * i % mod;
	}
	LL x = fct[MC];
	invfct[MC] = 1;
	for(int i = mod - 2 ; i > 0 ; i >>= 1){
		if(i % 2 == 1) (invfct[MC] *= x) %= mod;
		(x *= x) %= mod;
	}
	repm(i,MC,0){
		invfct[i-1] = invfct[i] * i % mod;
	}
}

LL func(int x , int y){
	return fct[x] * fct[x] % mod * invfct[y] % mod * invfct[x-y] % mod * invfct[x-y] % mod;
}

void dfs(int p , int q){
	bool b = 1;
	c[q] = 1;
	parent[q] = p;
	for(auto u : V[q]){
		if(u == p) continue;
		dfs(q,u);
		if(c[u]*2 >= N) b = 0;
		c[q] += c[u];
	}
	if(b && c[q] * 2 > N) g = q;
}

int main(){
	build();
	cin >> N;
	repp(i,1,N){
		int x,y;
		cin >> x >> y;
		V[x].PB(y);
		V[y].PB(x);
	}
	dfs(-1,1);
	if(g<0) return cout << fct[N/2] * fct[N/2] % mod << endl , 0;
	repp(i,0,N-c[g]+1) dp[0][i] = func(N-c[g],i);
	int z = 0;
	for(auto u : V[g]){
		if(u == parent[g]) continue;
		fill(dp[!z],dp[!z]+MC,0);
		repp(i,0,N+1){
			repp(j,0,c[u]+1){
				if(i+j>=N) break;
				(dp[!z][i+j] += dp[z][i] * func(c[u],j)) %= mod;
			}
		}
		z = !z;
	}
	LL ans = 0;
	int sgn = 1;
	repp(i,0,N){
		(ans += sgn * dp[z][i] * fct[N-i]) %= mod;
		sgn *= -1;
	}
	if(ans<0) ans += mod;
	cout << ans << endl;
	return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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>

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

const int MC = 5010;
const LL mod = 1e9 + 7;
int N;
vector<int> V[MC];
int c[MC],parent[MC];
int g = -1;
LL fct[MC+1];
LL invfct[MC+1];
LL dp[2][MC];

void build(){
	fct[0] = fct[1] = 1;
	repp(i,2,MC+1){
		fct[i] = fct[i-1] * i % mod;
	}
	LL x = fct[MC];
	invfct[MC] = 1;
	for(int i = mod - 2 ; i > 0 ; i >>= 1){
		if(i % 2 == 1) (invfct[MC] *= x) %= mod;
		(x *= x) %= mod;
	}
	repm(i,MC,0){
		invfct[i-1] = invfct[i] * i % mod;
	}
}

LL func(int x , int y){
	return fct[x] * fct[x] % mod * invfct[y] % mod * invfct[x-y] % mod * invfct[x-y] % mod;
}

void dfs(int p , int q){
	bool b = 1;
	c[q] = 1;
	parent[q] = p;
	for(auto u : V[q]){
		if(u == p) continue;
		dfs(q,u);
		if(c[u]*2 >= N) b = 0;
		c[q] += c[u];
	}
	if(b && c[q] * 2 > N) g = q;
}

int main(){
	build();
	cin >> N;
	repp(i,1,N){
		int x,y;
		cin >> x >> y;
		V[x].PB(y);
		V[y].PB(x);
	}
	dfs(-1,1);
	if(g<0) return cout << fct[N/2] * fct[N/2] % mod << endl , 0;
	repp(i,0,N-c[g]+1) dp[0][i] = func(N-c[g],i);
	int z = 0;
	for(auto u : V[g]){
		if(u == parent[g]) continue;
		fill(dp[!z],dp[!z]+MC,0);
		repp(i,0,N+1){
			repp(j,0,c[u]+1){
				if(i+j>=N) break;
				(dp[!z][i+j] += dp[z][i] * func(c[u],j)) %= mod;
			}
		}
		z = !z;
	}
	LL ans = 0;
	int sgn = 1;
	repp(i,0,N){
		(ans += sgn * dp[z][i] * fct[N-i]) %= mod;
		sgn *= -1;
	}
	if(ans<0) ans += mod;
	cout << ans << endl;
	return 0;
}

```