#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define MOD 1000000007
typedef long long ll; 
ll dp[5005], nxt[5005], fact[5005], inv[5005]; 
inline ll quick_pow(ll a, int n)
{
	ll res = 1; 
	while (n)
	{
		if (n & 1)
			res = res * a % MOD; 
		a = a * a % MOD; 
		n >>= 1; 
	}
	return res; 
}
inline ll C(int n, int m)
{
	return fact[n] * inv[m] % MOD * inv[n - m] % MOD; 
}
int lst[5005], to[10005], pre[10005], tot; 
int sz[5005], seq[5005], n; 
inline void add_edge(int u, int v)
{
	to[tot] = v; 
	pre[tot] = lst[u]; 
	lst[u] = tot++; 
}
void dfs(int u, int fa = -1)
{
	int mx = 0; 
	sz[u] = 1; 
	for (int i = lst[u]; ~i; i = pre[i])
	{
		if (to[i] == fa)
			continue; 
		dfs(to[i], u); 
		sz[u] += sz[to[i]]; 
		mx = std::max(mx, sz[to[i]]); 
	}
	mx = std::max(mx, n - sz[u]); 
	if (mx << 1 == n)
	{
		printf("%lld\n", fact[mx] * fact[mx] % MOD);
		exit(0); 
	}
	if (mx << 1 > n)
		return; 
	int cnt = 0, len = 0; 
	for (int i = lst[u]; ~i; i = pre[i])
	{
		if (to[i] != fa)
			seq[cnt++] = sz[to[i]]; 
	}
	if (u)
		seq[cnt++] = n - sz[u]; 
	memset(dp, 0, sizeof(dp)); 
	dp[0] = 1; 
	for (int i = 0; i < cnt; i++)
	{
		memset(nxt, 0, sizeof(nxt)); 
		for (int j = 0; j <= seq[i]; j++)
		{
			for (int k = 0; k <= len; k++)
				(nxt[j + k] += dp[k] * C(seq[i], j) % MOD * C(seq[i], j) % MOD * fact[j]) %= MOD; 
		}
		len += seq[i]; 
		memcpy(dp, nxt, sizeof(nxt)); 
	}
	ll ans = 0; 
	for (int i = 0; i <= len; i++)
		(ans += (i & 1 ? -1 : 1) * dp[i] * fact[n - i]) %= MOD; 
	printf("%lld\n", (ans + MOD) % MOD);
	exit(0); 
}
int main()
{
	// freopen("ARC087-F.in", "r", stdin); 
	memset(lst, -1, sizeof(lst)); 
	scanf("%d", &n); 
	for (int i = 1; i < n; i++)
	{
		int u, v; 
		scanf("%d%d", &u, &v); 
		add_edge(--u, --v); 
		add_edge(v, u); 
	}
	fact[0] = inv[0] = 1; 
	for (int i = 1; i <= n; i++)
	{
		fact[i] = fact[i - 1] * i % MOD; 
		inv[i] = quick_pow(fact[i], MOD - 2); 
	}
	dfs(0); 
	return 0; 
}

### Prompt

Create a solution in CPP for 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 <algorithm>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define MOD 1000000007
typedef long long ll; 
ll dp[5005], nxt[5005], fact[5005], inv[5005]; 
inline ll quick_pow(ll a, int n)
{
	ll res = 1; 
	while (n)
	{
		if (n & 1)
			res = res * a % MOD; 
		a = a * a % MOD; 
		n >>= 1; 
	}
	return res; 
}
inline ll C(int n, int m)
{
	return fact[n] * inv[m] % MOD * inv[n - m] % MOD; 
}
int lst[5005], to[10005], pre[10005], tot; 
int sz[5005], seq[5005], n; 
inline void add_edge(int u, int v)
{
	to[tot] = v; 
	pre[tot] = lst[u]; 
	lst[u] = tot++; 
}
void dfs(int u, int fa = -1)
{
	int mx = 0; 
	sz[u] = 1; 
	for (int i = lst[u]; ~i; i = pre[i])
	{
		if (to[i] == fa)
			continue; 
		dfs(to[i], u); 
		sz[u] += sz[to[i]]; 
		mx = std::max(mx, sz[to[i]]); 
	}
	mx = std::max(mx, n - sz[u]); 
	if (mx << 1 == n)
	{
		printf("%lld\n", fact[mx] * fact[mx] % MOD);
		exit(0); 
	}
	if (mx << 1 > n)
		return; 
	int cnt = 0, len = 0; 
	for (int i = lst[u]; ~i; i = pre[i])
	{
		if (to[i] != fa)
			seq[cnt++] = sz[to[i]]; 
	}
	if (u)
		seq[cnt++] = n - sz[u]; 
	memset(dp, 0, sizeof(dp)); 
	dp[0] = 1; 
	for (int i = 0; i < cnt; i++)
	{
		memset(nxt, 0, sizeof(nxt)); 
		for (int j = 0; j <= seq[i]; j++)
		{
			for (int k = 0; k <= len; k++)
				(nxt[j + k] += dp[k] * C(seq[i], j) % MOD * C(seq[i], j) % MOD * fact[j]) %= MOD; 
		}
		len += seq[i]; 
		memcpy(dp, nxt, sizeof(nxt)); 
	}
	ll ans = 0; 
	for (int i = 0; i <= len; i++)
		(ans += (i & 1 ? -1 : 1) * dp[i] * fact[n - i]) %= MOD; 
	printf("%lld\n", (ans + MOD) % MOD);
	exit(0); 
}
int main()
{
	// freopen("ARC087-F.in", "r", stdin); 
	memset(lst, -1, sizeof(lst)); 
	scanf("%d", &n); 
	for (int i = 1; i < n; i++)
	{
		int u, v; 
		scanf("%d%d", &u, &v); 
		add_edge(--u, --v); 
		add_edge(v, u); 
	}
	fact[0] = inv[0] = 1; 
	for (int i = 1; i <= n; i++)
	{
		fact[i] = fact[i - 1] * i % MOD; 
		inv[i] = quick_pow(fact[i], MOD - 2); 
	}
	dfs(0); 
	return 0; 
}

```