#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;
const int INF = 1 << 30;
const int MAXN = 5005;

struct Edge
{
	int to, next;
}e[MAXN*2];
int head[MAXN], te = 1;

inline void addE(int u, int v) 
{
	e[++te] = (Edge){v, head[u]}, head[u] = te;
}

long long g[MAXN][MAXN], fac[MAXN], inv[MAXN];

int fa[MAXN], sz[MAXN], n, x, y, r;

void Root()
{
	static int q[MAXN], val[MAXN], st = 0, ed = 1;
	q[0] = 1;
	while (st < ed)
	{
		int u = q[st++];
		for (int j = head[u]; j != 0; j = e[j].next)
			if (e[j].to != fa[u])
				fa[e[j].to] = u, q[ed++] = e[j].to;
	}
	int mn = INF;
	for (int i = n - 1; i >= 0; i--)
	{
		int u = q[i];
		sz[u] = 1, val[u] = 0;
		for (int j = head[u]; j != 0; j = e[j].next)
			if (fa[u] != e[j].to)
				sz[u] += sz[e[j].to], val[u] = max(val[u], sz[e[j].to]);
		val[u] = max(val[u], n - sz[u]);
		if (val[u] < mn)
			mn = val[u], r = u;
	}
}

void dfs(int u)
{
	sz[u] = 1;
	for (int j = head[u]; j != 0; j = e[j].next)
		if (e[j].to != fa[u])
			fa[e[j].to] = u, dfs(e[j].to), sz[u] += sz[e[j].to];
}

long long qpow(long long a, int b)
{
	long long ret = 1;
	while (b)
	{
		if (b & 1) ret = ret * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return ret;
}

void init()
{
	fac[0] = 1, inv[0] = 1;
	for (int i = 1; i <= n; i++)
		fac[i] = fac[i - 1] * i % MOD;
	for (int i = 1; i <= n; i++)
		inv[i] = qpow(fac[i], MOD - 2);
}

inline long long C(int n, int m)
{
	return fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}

inline long long A(int n, int m)
{
	return fac[n] * inv[n - m] % MOD;
}

int main() 
{
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		cin >> x >> y;
		addE(x, y), addE(y, x);
	}

	Root();

	memset(fa, 0, sizeof(fa));
	memset(sz, 0, sizeof(sz));
	dfs(r);

	int N;
	vector<int> S(1);
	for (int j = head[r]; j != 0; j = e[j].next)
		S.push_back(sz[e[j].to]);
	N = S.size() - 1;

	init();

	int H = 0;
	g[0][0] = 1;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 0; j <= S[i]; j++)
			for (int k = 0; k <= H; k++)
				g[i][j + k] += g[i - 1][k] * C(S[i], j) % MOD * A(S[i], j) % MOD, g[i][j + k] %= MOD;
		H += S[i];
	}
	
	long long res = fac[n];
	for (int k = 1; k < n; k++)
		res += qpow(-1, k) * g[N][k] * fac[n - k] % MOD, res %= MOD;
	if (res < 0)
		res += MOD;
	cout << res << endl;
	return 0;
}

### Prompt

Generate 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 <cstring>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;
const int INF = 1 << 30;
const int MAXN = 5005;

struct Edge
{
	int to, next;
}e[MAXN*2];
int head[MAXN], te = 1;

inline void addE(int u, int v) 
{
	e[++te] = (Edge){v, head[u]}, head[u] = te;
}

long long g[MAXN][MAXN], fac[MAXN], inv[MAXN];

int fa[MAXN], sz[MAXN], n, x, y, r;

void Root()
{
	static int q[MAXN], val[MAXN], st = 0, ed = 1;
	q[0] = 1;
	while (st < ed)
	{
		int u = q[st++];
		for (int j = head[u]; j != 0; j = e[j].next)
			if (e[j].to != fa[u])
				fa[e[j].to] = u, q[ed++] = e[j].to;
	}
	int mn = INF;
	for (int i = n - 1; i >= 0; i--)
	{
		int u = q[i];
		sz[u] = 1, val[u] = 0;
		for (int j = head[u]; j != 0; j = e[j].next)
			if (fa[u] != e[j].to)
				sz[u] += sz[e[j].to], val[u] = max(val[u], sz[e[j].to]);
		val[u] = max(val[u], n - sz[u]);
		if (val[u] < mn)
			mn = val[u], r = u;
	}
}

void dfs(int u)
{
	sz[u] = 1;
	for (int j = head[u]; j != 0; j = e[j].next)
		if (e[j].to != fa[u])
			fa[e[j].to] = u, dfs(e[j].to), sz[u] += sz[e[j].to];
}

long long qpow(long long a, int b)
{
	long long ret = 1;
	while (b)
	{
		if (b & 1) ret = ret * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return ret;
}

void init()
{
	fac[0] = 1, inv[0] = 1;
	for (int i = 1; i <= n; i++)
		fac[i] = fac[i - 1] * i % MOD;
	for (int i = 1; i <= n; i++)
		inv[i] = qpow(fac[i], MOD - 2);
}

inline long long C(int n, int m)
{
	return fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}

inline long long A(int n, int m)
{
	return fac[n] * inv[n - m] % MOD;
}

int main() 
{
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		cin >> x >> y;
		addE(x, y), addE(y, x);
	}

	Root();

	memset(fa, 0, sizeof(fa));
	memset(sz, 0, sizeof(sz));
	dfs(r);

	int N;
	vector<int> S(1);
	for (int j = head[r]; j != 0; j = e[j].next)
		S.push_back(sz[e[j].to]);
	N = S.size() - 1;

	init();

	int H = 0;
	g[0][0] = 1;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 0; j <= S[i]; j++)
			for (int k = 0; k <= H; k++)
				g[i][j + k] += g[i - 1][k] * C(S[i], j) % MOD * A(S[i], j) % MOD, g[i][j + k] %= MOD;
		H += S[i];
	}
	
	long long res = fac[n];
	for (int k = 1; k < n; k++)
		res += qpow(-1, k) * g[N][k] * fac[n - k] % MOD, res %= MOD;
	if (res < 0)
		res += MOD;
	cout << res << endl;
	return 0;
}

```