#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll mod = 1000000007;
ll dp[5151][5151];
vector<int>pat[5151];
bool flag[5151];
int num;
int cent;
int dfs(int node)
{
	if (flag[node])return 0;
	flag[node] = true;
	int s = 1, maxi = 0;
	for (int i = 0; i < pat[node].size(); i++)
	{
		int r = dfs(pat[node][i]);
		maxi = max(maxi, r);
		s += r;
	}
	if ((num - s) * 2 <= num&&maxi * 2 <= num)
	{
		if (cent == -1)cent = node;
		else
		{
			ll ans = 1;
			for (int i = 1; i <= num / 2; i++)ans = ans*i%mod*i%mod;
			printf("%lld\n", ans);
			exit(0);
		}
	}
	return s;
}
#define SIZE 100000
ll inv[SIZE + 1];
ll kai[SIZE + 1];
ll invkai[SIZE + 1];
void invinit()
{
	inv[1] = 1;
	for (int i = 2; i <= SIZE; i++)
	{
		inv[i] = mod - (mod / i)*inv[mod%i] % mod;
	}
	kai[0] = invkai[0] = 1;
	for (int i = 1; i <= SIZE; i++)
	{
		kai[i] = kai[i - 1] * i%mod;
		invkai[i] = invkai[i - 1] * inv[i] % mod;
	}
}
ll com(ll a, ll b)
{
	if (b < 0 || a < b)return 0;
	return (invkai[b] * invkai[a - b]) % mod*kai[a] % mod;
}
int main()
{
	scanf("%d", &num);
	invinit();
	for (int i = 0; i < num - 1; i++)
	{
		int za, zb;
		scanf("%d%d", &za, &zb);
		za--, zb--;
		pat[za].push_back(zb);
		pat[zb].push_back(za);
	}
	cent = -1;
	dfs(0);
	vector<int>v;
	fill(flag, flag + num, false);
	flag[cent] = true;
	for (int i = 0; i < pat[cent].size(); i++)v.push_back(dfs(pat[cent][i]));
	dp[0][0] = 1;
	for (int i = 0; i < v.size(); i++)
	{
		for (int j = 0; j <= num; j++)
		{
			if (dp[i][j] == 0)continue;
			ll now = 1;
			for (int k = 0; k <= v[i]; k++)
			{
				dp[i + 1][j + k] = (dp[i + 1][j + k] + dp[i][j] * now%mod*com(v[i], k)) % mod;
				now *= v[i] - k;
				now %= mod;
			}
		}
	}
	ll ans = 0;
	for (int i = 0; i <= num; i++)
	{
		ll t = dp[v.size()][i] * kai[num - i] % mod;
		//printf("%lld\n", dp[v.size()][i]);
		if (i % 2 == 0)ans += t;
		else ans += mod - t;
	}
	printf("%lld\n", ans%mod);
}
### 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<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll mod = 1000000007;
ll dp[5151][5151];
vector<int>pat[5151];
bool flag[5151];
int num;
int cent;
int dfs(int node)
{
	if (flag[node])return 0;
	flag[node] = true;
	int s = 1, maxi = 0;
	for (int i = 0; i < pat[node].size(); i++)
	{
		int r = dfs(pat[node][i]);
		maxi = max(maxi, r);
		s += r;
	}
	if ((num - s) * 2 <= num&&maxi * 2 <= num)
	{
		if (cent == -1)cent = node;
		else
		{
			ll ans = 1;
			for (int i = 1; i <= num / 2; i++)ans = ans*i%mod*i%mod;
			printf("%lld\n", ans);
			exit(0);
		}
	}
	return s;
}
#define SIZE 100000
ll inv[SIZE + 1];
ll kai[SIZE + 1];
ll invkai[SIZE + 1];
void invinit()
{
	inv[1] = 1;
	for (int i = 2; i <= SIZE; i++)
	{
		inv[i] = mod - (mod / i)*inv[mod%i] % mod;
	}
	kai[0] = invkai[0] = 1;
	for (int i = 1; i <= SIZE; i++)
	{
		kai[i] = kai[i - 1] * i%mod;
		invkai[i] = invkai[i - 1] * inv[i] % mod;
	}
}
ll com(ll a, ll b)
{
	if (b < 0 || a < b)return 0;
	return (invkai[b] * invkai[a - b]) % mod*kai[a] % mod;
}
int main()
{
	scanf("%d", &num);
	invinit();
	for (int i = 0; i < num - 1; i++)
	{
		int za, zb;
		scanf("%d%d", &za, &zb);
		za--, zb--;
		pat[za].push_back(zb);
		pat[zb].push_back(za);
	}
	cent = -1;
	dfs(0);
	vector<int>v;
	fill(flag, flag + num, false);
	flag[cent] = true;
	for (int i = 0; i < pat[cent].size(); i++)v.push_back(dfs(pat[cent][i]));
	dp[0][0] = 1;
	for (int i = 0; i < v.size(); i++)
	{
		for (int j = 0; j <= num; j++)
		{
			if (dp[i][j] == 0)continue;
			ll now = 1;
			for (int k = 0; k <= v[i]; k++)
			{
				dp[i + 1][j + k] = (dp[i + 1][j + k] + dp[i][j] * now%mod*com(v[i], k)) % mod;
				now *= v[i] - k;
				now %= mod;
			}
		}
	}
	ll ans = 0;
	for (int i = 0; i <= num; i++)
	{
		ll t = dp[v.size()][i] * kai[num - i] % mod;
		//printf("%lld\n", dp[v.size()][i]);
		if (i % 2 == 0)ans += t;
		else ans += mod - t;
	}
	printf("%lld\n", ans%mod);
}
```