#ifndef LOCAL
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

typedef long long ll;
typedef long long llong;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;

const ll MOD = 1e9 + 7;

ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
const int MAXN = 5100;

int sz[MAXN];
int n;
vector<int> eds[MAXN];

void dfs1(int v, int p = -1) {
	sz[v] = 1;
	for (int u: eds[v]) {
		if (u == p)
			continue;
		dfs1(u, v);
		sz[v] += sz[u];
	}
}

ll fc[MAXN];
ll bfc[MAXN];
ll dp[MAXN];
ll dp2[MAXN];

void add(ll &a, ll b) {
	a += b;
	a %= MOD;
}

int main() {
	cin >> n;
	fc[0] = 1;
	for (int i = 1; i <= n; ++i)
		fc[i] = (fc[i - 1] * i) % MOD;
	for (int i = 0; i <= n; ++i)
		bfc[i] = pw(fc[i], MOD - 2);
	for (int i = 0; i < n - 1; ++i) {
		int a, b;
		cin >> a >> b;
		--a, --b;
		eds[a].push_back(b);
		eds[b].push_back(a);
	}
	dfs1(0);
	int bst = -1;
	for (int i = 0; i < n; ++i) {
		if (sz[i] * 2 >= n && (bst == -1 || sz[i] < sz[bst]))
			bst = i;
	}
	vector<int> vv;
	for (int u: eds[bst]) {
		if (sz[u] < sz[bst])
			vv.push_back(sz[u]);
		else
			vv.push_back(n - sz[bst]);
	}
	dp[0] = 1;
	for (int i: vv) {
		for (int j = 0; j <= n; ++j)
			dp2[j] = 0;
		for (int j = 0; j <= n; ++j) {
			if (dp[j] == 0)
				continue;
			for (int k = 0; k <= i; ++k)
				add(dp2[j + k], dp[j] * fc[i] % MOD * fc[i] % MOD * bfc[k] % MOD * bfc[i - k] % MOD * bfc[i - k] % MOD);
		}
		for (int j = 0; j <= n; ++j)
			dp[j] = dp2[j];
	}
	ll ans = 0;
	for (int i = 0; i <= n; ++i) {
		if (i % 2 == 0)
			add(ans, dp[i] * fc[n - i] % MOD);
		else
			add(ans, MOD - dp[i] * fc[n - i] % MOD);
	}
	cout << ans << "\n";
	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
#ifndef LOCAL
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

typedef long long ll;
typedef long long llong;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;

const ll MOD = 1e9 + 7;

ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
const int MAXN = 5100;

int sz[MAXN];
int n;
vector<int> eds[MAXN];

void dfs1(int v, int p = -1) {
	sz[v] = 1;
	for (int u: eds[v]) {
		if (u == p)
			continue;
		dfs1(u, v);
		sz[v] += sz[u];
	}
}

ll fc[MAXN];
ll bfc[MAXN];
ll dp[MAXN];
ll dp2[MAXN];

void add(ll &a, ll b) {
	a += b;
	a %= MOD;
}

int main() {
	cin >> n;
	fc[0] = 1;
	for (int i = 1; i <= n; ++i)
		fc[i] = (fc[i - 1] * i) % MOD;
	for (int i = 0; i <= n; ++i)
		bfc[i] = pw(fc[i], MOD - 2);
	for (int i = 0; i < n - 1; ++i) {
		int a, b;
		cin >> a >> b;
		--a, --b;
		eds[a].push_back(b);
		eds[b].push_back(a);
	}
	dfs1(0);
	int bst = -1;
	for (int i = 0; i < n; ++i) {
		if (sz[i] * 2 >= n && (bst == -1 || sz[i] < sz[bst]))
			bst = i;
	}
	vector<int> vv;
	for (int u: eds[bst]) {
		if (sz[u] < sz[bst])
			vv.push_back(sz[u]);
		else
			vv.push_back(n - sz[bst]);
	}
	dp[0] = 1;
	for (int i: vv) {
		for (int j = 0; j <= n; ++j)
			dp2[j] = 0;
		for (int j = 0; j <= n; ++j) {
			if (dp[j] == 0)
				continue;
			for (int k = 0; k <= i; ++k)
				add(dp2[j + k], dp[j] * fc[i] % MOD * fc[i] % MOD * bfc[k] % MOD * bfc[i - k] % MOD * bfc[i - k] % MOD);
		}
		for (int j = 0; j <= n; ++j)
			dp[j] = dp2[j];
	}
	ll ans = 0;
	for (int i = 0; i <= n; ++i) {
		if (i % 2 == 0)
			add(ans, dp[i] * fc[n - i] % MOD);
		else
			add(ans, MOD - dp[i] * fc[n - i] % MOD);
	}
	cout << ans << "\n";
	return 0;
}



```