#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
typedef long long ll;

const int MOD = 1000000007;

ll pw(ll n) { return n * n % MOD; }
ll pw(ll n, ll k) {
	ll r = 1; for(n %= MOD; k; k >>= 1) {
		if(k&1) r = r * n % MOD;
		n = n * n % MOD;
	}
	return r;
}
ll inv(ll n) { return pw(n, MOD-2); }

const int MAXN = 5005;

vector<int> G[MAXN];

int cnt[MAXN];

ll Ans;
int N, Rt;

void dfs(int i) {
	cnt[i] = 1;
	for(int v : G[i]) if(!cnt[v]) {
		dfs(v);
		cnt[i] += cnt[v];
	}
}

void cent(int &rt) {
	const int N = cnt[rt];
	for(int hi, hc;;) {
		hi = hc = -1;
		for(int v : G[rt]) if(cnt[v] < N) {
			if(cnt[v] <= hc) continue;
			hc = cnt[v]; hi = v;
		}
		if(hc*2 <= N) break;
		cnt[rt] = N - hc;
		cnt[hi] = N;
		rt = hi;
	}
}

ll D[2][MAXN];
ll F[MAXN], RF[MAXN];

int main() {
	ios::sync_with_stdio(false);

	cin >> N;
	for(int i = 1, a, b; i < N; i++) {
		cin >> a >> b;
		G[a].eb(b);
		G[b].eb(a);
	}

	dfs(1);
	Rt = 1; cent(Rt);

	F[0] = 1;
	for(int i = 1; i <= N; i++) F[i] = F[i-1] * i % MOD;
	RF[N] = inv(F[N]);
	for(int i = N; i--;) RF[i] = RF[i+1] * (i+1) % MOD;

	memset(D[0], 0, MAXN<<3);
	D[0][0] = 1;
	int sum = 0;
	for(int v : G[Rt]) {
		memset(D[1], 0, MAXN<<3);
		int c = cnt[v];
		for(int j = 0; j <= sum; j++) {
			for(int l = 0; l <= c; l++) {
				D[1][j+l] += D[0][j] * pw(F[c]) % MOD * RF[l] % MOD * pw(RF[c-l]);
				D[1][j+l] %= MOD;
			}
		}
		memcpy(D[0], D[1], MAXN<<3);
		sum += c;
	}

	for(int k = 0; k < N; k++)
		Ans += D[0][k] * F[N-k] * ((k&1) ? -1 : 1) % MOD;
	
	cout << ((Ans % MOD + MOD) % MOD) << endl;
	return 0;
}
### Prompt

Please create a solution in Cpp 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>
#define eb emplace_back
using namespace std;
typedef long long ll;

const int MOD = 1000000007;

ll pw(ll n) { return n * n % MOD; }
ll pw(ll n, ll k) {
	ll r = 1; for(n %= MOD; k; k >>= 1) {
		if(k&1) r = r * n % MOD;
		n = n * n % MOD;
	}
	return r;
}
ll inv(ll n) { return pw(n, MOD-2); }

const int MAXN = 5005;

vector<int> G[MAXN];

int cnt[MAXN];

ll Ans;
int N, Rt;

void dfs(int i) {
	cnt[i] = 1;
	for(int v : G[i]) if(!cnt[v]) {
		dfs(v);
		cnt[i] += cnt[v];
	}
}

void cent(int &rt) {
	const int N = cnt[rt];
	for(int hi, hc;;) {
		hi = hc = -1;
		for(int v : G[rt]) if(cnt[v] < N) {
			if(cnt[v] <= hc) continue;
			hc = cnt[v]; hi = v;
		}
		if(hc*2 <= N) break;
		cnt[rt] = N - hc;
		cnt[hi] = N;
		rt = hi;
	}
}

ll D[2][MAXN];
ll F[MAXN], RF[MAXN];

int main() {
	ios::sync_with_stdio(false);

	cin >> N;
	for(int i = 1, a, b; i < N; i++) {
		cin >> a >> b;
		G[a].eb(b);
		G[b].eb(a);
	}

	dfs(1);
	Rt = 1; cent(Rt);

	F[0] = 1;
	for(int i = 1; i <= N; i++) F[i] = F[i-1] * i % MOD;
	RF[N] = inv(F[N]);
	for(int i = N; i--;) RF[i] = RF[i+1] * (i+1) % MOD;

	memset(D[0], 0, MAXN<<3);
	D[0][0] = 1;
	int sum = 0;
	for(int v : G[Rt]) {
		memset(D[1], 0, MAXN<<3);
		int c = cnt[v];
		for(int j = 0; j <= sum; j++) {
			for(int l = 0; l <= c; l++) {
				D[1][j+l] += D[0][j] * pw(F[c]) % MOD * RF[l] % MOD * pw(RF[c-l]);
				D[1][j+l] %= MOD;
			}
		}
		memcpy(D[0], D[1], MAXN<<3);
		sum += c;
	}

	for(int k = 0; k < N; k++)
		Ans += D[0][k] * F[N-k] * ((k&1) ? -1 : 1) % MOD;
	
	cout << ((Ans % MOD + MOD) % MOD) << endl;
	return 0;
}
```