#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

vector <ll> T[5050];
ll S[5050];
ll F[5050], FI[5050], I[5050];
ll D[5050], E[5050];
ll n, p, ans;

ll pow(ll a, ll b)
{
	ll ret = 1;
	
	for(; b; b>>=1){
		if(b & 1) ret = ret * a % mod;
		a = a * a % mod;
	}
	
	return ret;
}

void dfs(ll p, ll r)
{
	S[p] = 1;
	
	for(ll &t: T[p]){
		if(t != r){
			dfs(t, p);
			S[p] += S[t];
		}
	}
}

int main()
{
	ll i, j, m, s, t, u, v;
	
	scanf("%lld", &n);
	
	F[0] = FI[0] = 1;
	
	for(i=1; i<=n; i++){
		F[i] = F[i - 1] * i % mod;
		I[i] = pow(i, mod - 2);
		FI[i] = FI[i - 1] * I[i] % mod;
	}
	
	for(i=1; i<n; i++){
		scanf("%lld%lld", &u, &v);
		T[u].push_back(v);
		T[v].push_back(u);
	}
	
	dfs(1, 0);
	
	for(p=1; ; ){
		m = -1;
		for(ll &t: T[p]){
			if(S[t] > S[p]) continue;
			if(m == -1 || S[m] < S[t]) m = t;
		}
		
		if(m == -1 || S[m] + S[m] <= n) break;
		p = m;
	}
	
	D[0] = 1;
	
	for(ll &t: T[p]){
		dfs(t, p); s = S[t];
		
		for(i=0; i<=s; i++){
			for(j=0; j<=n-i; j++){
				t = D[j] * F[s] % mod * FI[s - i] % mod;
				t = t * F[s] % mod * FI[s - i] % mod * FI[i] % mod;
				E[j + i] = (E[j + i] + t) % mod;
			}
		}
		
		for(i=0; i<=n; i++){
			D[i] = E[i]; E[i] = 0;
		}
	}
	
	for(i=0; i<=n; i++){
		if(i & 1) ans = (ans - D[i] * F[n - i] % mod + mod) % mod;
		else ans = (ans + D[i] * F[n - i]) % mod;
	}
	
	printf("%lld\n", ans);
	
	return 0;
}
### 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 <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

vector <ll> T[5050];
ll S[5050];
ll F[5050], FI[5050], I[5050];
ll D[5050], E[5050];
ll n, p, ans;

ll pow(ll a, ll b)
{
	ll ret = 1;
	
	for(; b; b>>=1){
		if(b & 1) ret = ret * a % mod;
		a = a * a % mod;
	}
	
	return ret;
}

void dfs(ll p, ll r)
{
	S[p] = 1;
	
	for(ll &t: T[p]){
		if(t != r){
			dfs(t, p);
			S[p] += S[t];
		}
	}
}

int main()
{
	ll i, j, m, s, t, u, v;
	
	scanf("%lld", &n);
	
	F[0] = FI[0] = 1;
	
	for(i=1; i<=n; i++){
		F[i] = F[i - 1] * i % mod;
		I[i] = pow(i, mod - 2);
		FI[i] = FI[i - 1] * I[i] % mod;
	}
	
	for(i=1; i<n; i++){
		scanf("%lld%lld", &u, &v);
		T[u].push_back(v);
		T[v].push_back(u);
	}
	
	dfs(1, 0);
	
	for(p=1; ; ){
		m = -1;
		for(ll &t: T[p]){
			if(S[t] > S[p]) continue;
			if(m == -1 || S[m] < S[t]) m = t;
		}
		
		if(m == -1 || S[m] + S[m] <= n) break;
		p = m;
	}
	
	D[0] = 1;
	
	for(ll &t: T[p]){
		dfs(t, p); s = S[t];
		
		for(i=0; i<=s; i++){
			for(j=0; j<=n-i; j++){
				t = D[j] * F[s] % mod * FI[s - i] % mod;
				t = t * F[s] % mod * FI[s - i] % mod * FI[i] % mod;
				E[j + i] = (E[j + i] + t) % mod;
			}
		}
		
		for(i=0; i<=n; i++){
			D[i] = E[i]; E[i] = 0;
		}
	}
	
	for(i=0; i<=n; i++){
		if(i & 1) ans = (ans - D[i] * F[n - i] % mod + mod) % mod;
		else ans = (ans + D[i] * F[n - i]) % mod;
	}
	
	printf("%lld\n", ans);
	
	return 0;
}
```