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

typedef long long LL;
using namespace std;
const int maxn = 5010, maxm = 10010, mod = 1e9 + 7;

int read()
{
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)) { if(c == '-') f = 0; c = getchar(); }
	while(isdigit(c)) { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
	return f ? x : -x;
}

int to[maxm], nxt[maxm], head[maxn], e;
int sz[maxn], now, fac[maxn], ifac[maxn], inv[maxn];
int f[2][maxn], n;
vector<int> rt;

void add(int x, int y) 
{ 
	to[++e] = y; nxt[e] = head[x]; head[x] = e; 
	to[++e] = x; nxt[e] = head[y]; head[y] = e;
}

void dfs(int u, int fa)
{
	int Mn = 0; sz[u] = 1;
	for(int i = head[u]; i; i = nxt[i])
	{
		int v = to[i];
		if(v == fa) continue;
		dfs(v, u); sz[u] += sz[v];
		Mn = max(Mn, sz[v]);
	}
	Mn = max(Mn, n - sz[u]);
	if(Mn == now) { rt.push_back(u); }
	else if(Mn < now) { rt.clear(); rt.push_back(u); now = Mn; }
}

void init(int N)
{
	fac[0] = fac[1] = ifac[0] = ifac[1] = inv[0] = inv[1] = 1;
	for(int i = 2; i <= N; ++i)
	{
		fac[i] = (LL)fac[i - 1] * i % mod;
		inv[i] = (LL)(mod - mod / i) * inv[mod % i] % mod;
		ifac[i] = (LL)ifac[i - 1] * inv[i] % mod;
	}
}

void Add(int &x, int y) { x += y; x = (x >= mod ? x - mod : x); }

int C(int N, int M)
{
	if(N < M) return 0;
	return (LL)fac[N] * ifac[M] % mod * ifac[N - M] % mod;
}

int main()
{
	
	n = read();
	for(int i = 1; i < n; ++i) add(read(), read());

	init(n);

	now = 0x3f3f3f3f; dfs(1, 0);
	if(rt.size() == 2) { cout << (LL)fac[n / 2] * fac[n / 2] % mod << endl; return 0; }
	else
	{
		int u = rt[0];
		int p = 0, q = 1; f[0][0] = 1;
		for(int i = head[u]; i; i = nxt[i])
		{
			int v = to[i];
			dfs(v, u);
			swap(p, q); for(int j = 0; j <= n; ++j) f[p][j] = 0;
			for(int k = 0; k <= n; ++k) if(f[q][k])
				for(int j = 0; j <= sz[v]; ++j)
					Add(f[p][k + j], (LL)f[q][k] * C(sz[v], j) % mod * fac[j] % mod * C(sz[v], j) % mod);
		}

		int ans = 0, coef = 1;
		for(int i = 0; i <= n; ++i, coef = mod - coef)
			Add(ans, (LL)coef * f[p][i] % mod * fac[n - i] % mod);
		cout << ans << endl;
	}

	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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

typedef long long LL;
using namespace std;
const int maxn = 5010, maxm = 10010, mod = 1e9 + 7;

int read()
{
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)) { if(c == '-') f = 0; c = getchar(); }
	while(isdigit(c)) { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
	return f ? x : -x;
}

int to[maxm], nxt[maxm], head[maxn], e;
int sz[maxn], now, fac[maxn], ifac[maxn], inv[maxn];
int f[2][maxn], n;
vector<int> rt;

void add(int x, int y) 
{ 
	to[++e] = y; nxt[e] = head[x]; head[x] = e; 
	to[++e] = x; nxt[e] = head[y]; head[y] = e;
}

void dfs(int u, int fa)
{
	int Mn = 0; sz[u] = 1;
	for(int i = head[u]; i; i = nxt[i])
	{
		int v = to[i];
		if(v == fa) continue;
		dfs(v, u); sz[u] += sz[v];
		Mn = max(Mn, sz[v]);
	}
	Mn = max(Mn, n - sz[u]);
	if(Mn == now) { rt.push_back(u); }
	else if(Mn < now) { rt.clear(); rt.push_back(u); now = Mn; }
}

void init(int N)
{
	fac[0] = fac[1] = ifac[0] = ifac[1] = inv[0] = inv[1] = 1;
	for(int i = 2; i <= N; ++i)
	{
		fac[i] = (LL)fac[i - 1] * i % mod;
		inv[i] = (LL)(mod - mod / i) * inv[mod % i] % mod;
		ifac[i] = (LL)ifac[i - 1] * inv[i] % mod;
	}
}

void Add(int &x, int y) { x += y; x = (x >= mod ? x - mod : x); }

int C(int N, int M)
{
	if(N < M) return 0;
	return (LL)fac[N] * ifac[M] % mod * ifac[N - M] % mod;
}

int main()
{
	
	n = read();
	for(int i = 1; i < n; ++i) add(read(), read());

	init(n);

	now = 0x3f3f3f3f; dfs(1, 0);
	if(rt.size() == 2) { cout << (LL)fac[n / 2] * fac[n / 2] % mod << endl; return 0; }
	else
	{
		int u = rt[0];
		int p = 0, q = 1; f[0][0] = 1;
		for(int i = head[u]; i; i = nxt[i])
		{
			int v = to[i];
			dfs(v, u);
			swap(p, q); for(int j = 0; j <= n; ++j) f[p][j] = 0;
			for(int k = 0; k <= n; ++k) if(f[q][k])
				for(int j = 0; j <= sz[v]; ++j)
					Add(f[p][k + j], (LL)f[q][k] * C(sz[v], j) % mod * fac[j] % mod * C(sz[v], j) % mod);
		}

		int ans = 0, coef = 1;
		for(int i = 0; i <= n; ++i, coef = mod - coef)
			Add(ans, (LL)coef * f[p][i] % mod * fac[n - i] % mod);
		cout << ans << endl;
	}

	return 0;
}
```