#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif

typedef long long ll;
typedef pair<int, int> pii;
#define mp make_pair

const int MOD = (int)1e9 + 7;
int add(int x, int y) {
	x += y;
	if (x >= MOD) return x - MOD;
	return x;
}
int sub(int x, int y) {
	x -= y;
	if (x < 0) return x + MOD;
	return x;
}
int mult(int x, int y) {
	return ((ll)x * y) % MOD;
}

const int N = 5002;
int C[N][N];
int f[N];
int n;
vector<int> g[N];
int sz[N];
int a[N];
int m;
int dp[2][N];

void dfs(int v, int par) {
	sz[v] = 1;
	for (int u : g[v]) {
		if (u == par) continue;
		dfs(u, v);
		sz[v] += sz[u];
	}
}

void solve() {
	dp[0][0] = 1;
	for (int i = 0; i < m; i++) {
		for (int x = 0; x <= n; x++)
			dp[1][x] = 0;
		for (int x = 0; x <= n; x++) {
			if (dp[0][x] == 0) continue;
			for (int y = 0; y <= a[i]; y++)
				dp[1][x + y] = add(dp[1][x + y], mult(mult(dp[0][x], f[y]), mult(C[a[i]][y], C[a[i]][y])));
		}
		for (int x = 0; x <= n; x++)
			dp[0][x] = dp[1][x];
	}
	int ans = 0;
	for (int x = 0; x <= n; x++) {
		int val = mult(dp[0][x], f[n - x]);
		if (x & 1)
			ans = sub(ans, val);
		else
			ans = add(ans, val);
	}
	printf("%d\n", ans);
}

int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	for (int i = 0; i < N; i++)
		C[i][0] = C[i][i] = 1;
	for (int i = 0; i < N; i++)
		for (int j = 1; j < i; j++)
			C[i][j] = add(C[i - 1][j - 1], C[i - 1][j]);
	f[0] = 1;
	for (int i = 1; i < N; i++)
		f[i] = mult(f[i - 1], i);

	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int v, u;
		scanf("%d%d", &v, &u);
		v--;u--;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	dfs(0, -1);
	int v = 0;
	while(true) {
		int w = -1;
		for (int u : g[v]) {
			if (sz[u] > sz[v]) continue;
			if (2 * sz[u] >= n)
				w = u;
		}
		if (w == -1) break;
		v = w;
	}
	dfs(v, -1);
	for (int u : g[v]) {
		a[m] = sz[u];
		if (2 * a[m] > n) throw;
		if (2 * a[m] == n) {
			printf("%d\n", mult(f[a[m]], f[a[m]]));
			return 0;
		}
		m++;
	}
	solve();

	return 0;
}

### Prompt

Your task is to create 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 <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif

typedef long long ll;
typedef pair<int, int> pii;
#define mp make_pair

const int MOD = (int)1e9 + 7;
int add(int x, int y) {
	x += y;
	if (x >= MOD) return x - MOD;
	return x;
}
int sub(int x, int y) {
	x -= y;
	if (x < 0) return x + MOD;
	return x;
}
int mult(int x, int y) {
	return ((ll)x * y) % MOD;
}

const int N = 5002;
int C[N][N];
int f[N];
int n;
vector<int> g[N];
int sz[N];
int a[N];
int m;
int dp[2][N];

void dfs(int v, int par) {
	sz[v] = 1;
	for (int u : g[v]) {
		if (u == par) continue;
		dfs(u, v);
		sz[v] += sz[u];
	}
}

void solve() {
	dp[0][0] = 1;
	for (int i = 0; i < m; i++) {
		for (int x = 0; x <= n; x++)
			dp[1][x] = 0;
		for (int x = 0; x <= n; x++) {
			if (dp[0][x] == 0) continue;
			for (int y = 0; y <= a[i]; y++)
				dp[1][x + y] = add(dp[1][x + y], mult(mult(dp[0][x], f[y]), mult(C[a[i]][y], C[a[i]][y])));
		}
		for (int x = 0; x <= n; x++)
			dp[0][x] = dp[1][x];
	}
	int ans = 0;
	for (int x = 0; x <= n; x++) {
		int val = mult(dp[0][x], f[n - x]);
		if (x & 1)
			ans = sub(ans, val);
		else
			ans = add(ans, val);
	}
	printf("%d\n", ans);
}

int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	for (int i = 0; i < N; i++)
		C[i][0] = C[i][i] = 1;
	for (int i = 0; i < N; i++)
		for (int j = 1; j < i; j++)
			C[i][j] = add(C[i - 1][j - 1], C[i - 1][j]);
	f[0] = 1;
	for (int i = 1; i < N; i++)
		f[i] = mult(f[i - 1], i);

	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int v, u;
		scanf("%d%d", &v, &u);
		v--;u--;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	dfs(0, -1);
	int v = 0;
	while(true) {
		int w = -1;
		for (int u : g[v]) {
			if (sz[u] > sz[v]) continue;
			if (2 * sz[u] >= n)
				w = u;
		}
		if (w == -1) break;
		v = w;
	}
	dfs(v, -1);
	for (int u : g[v]) {
		a[m] = sz[u];
		if (2 * a[m] > n) throw;
		if (2 * a[m] == n) {
			printf("%d\n", mult(f[a[m]], f[a[m]]));
			return 0;
		}
		m++;
	}
	solve();

	return 0;
}

```