#include <algorithm>
#include <assert.h>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define MOD 1000000007LL
#define MX 5005

using namespace std;

typedef long long ll;

template <typename T> void read(T& x)
{
	x = 0; char c = getchar(); bool f = 0;
	while(!isdigit(c) && c!='-') c = getchar();
	if(c == '-') f = 1, c = getchar();
	while(isdigit(c)) x = x*10+c-'0', c = getchar();
	if(f) x = -x;
}

int n;
int fst[MX], nxt[MX*2], v[MX*2], lnum;
ll fac[MX], faci[MX], inv[MX];
int siz[MX], mxs[MX], cen, cnt;
int sbt[MX], sum[MX], snm;
ll f[MX][MX];

void addeg(int nu, int nv)
{
	nxt[++lnum] = fst[nu];
	fst[nu] = lnum;
	v[lnum] = nv;
}

void input()
{
	int a, b;
	read(n);
	for(int i=1; i<n; i++)
	{
		read(a); read(b);
		addeg(a, b);
		addeg(b, a);
	}
	fac[0] = faci[0] = inv[0] = inv[1] = 1;
	for(int i=2; i<=n; i++) inv[i] = (MOD - MOD/i) * inv[MOD%i] % MOD;
	for(int i=1; i<=n; i++) fac[i] = fac[i-1] * i % MOD, faci[i] = faci[i-1] * inv[i] % MOD;
}

void dfs(int x, int f)
{
	siz[x] = 1;
	for(int i=fst[x]; i; i=nxt[i])
	{
		if(v[i] != f)
		{
			dfs(v[i], x);
			siz[x] += siz[v[i]];
			mxs[x] = max(mxs[x], siz[v[i]]);
		}
	}
	mxs[x] = max(mxs[x], n-siz[x]);
	if(!cen || mxs[x]<mxs[cen]) cen = x, cnt = 1;
	else if(mxs[x] == mxs[cen]) cnt++;
}

void work()
{
	dfs(1, 0);
	assert(cnt <= 2);
	if(cnt > 1) sbt[1] = sbt[2] = n/2, snm = 2;
	else
	{
		for(int i=fst[cen]; i; i=nxt[i])
			if(siz[v[i]] < siz[cen])
				sbt[++snm] = siz[v[i]];
		sbt[++snm] = n-siz[cen];
	}
	sort(sbt+1, sbt+snm+1);
	f[0][0] = 1;
	for(int i=1; i<=snm; i++) sum[i] = sum[i-1] + sbt[i];
	for(int i=1; i<=snm; i++)
	{
		for(int j=0; j<=sum[i]; j++)
		{
			for(int k=0; k<=sbt[i]&&k<=j; k++)
			{
				ll f2 = fac[sbt[i]] * fac[sbt[i]] % MOD;
				ll d2 = faci[sbt[i]-k] * faci[sbt[i]-k] % MOD;
				ll d = faci[k] % MOD;
				f[i][j] = (f[i][j] + f[i-1][j-k] * f2 % MOD *d2 % MOD * d) % MOD;
			}
		}
	}
	ll ans = 0;
	for(int i=0; i<=n; i++)
		if(i & 1) ans = (ans + MOD*MOD - f[snm][i]*fac[n-i]) % MOD;
		else ans = (ans + f[snm][i]*fac[n-i]) % MOD;
	printf("%lld\n", ans);
}
int main()
{
	input();
	work();
	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 <algorithm>
#include <assert.h>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define MOD 1000000007LL
#define MX 5005

using namespace std;

typedef long long ll;

template <typename T> void read(T& x)
{
	x = 0; char c = getchar(); bool f = 0;
	while(!isdigit(c) && c!='-') c = getchar();
	if(c == '-') f = 1, c = getchar();
	while(isdigit(c)) x = x*10+c-'0', c = getchar();
	if(f) x = -x;
}

int n;
int fst[MX], nxt[MX*2], v[MX*2], lnum;
ll fac[MX], faci[MX], inv[MX];
int siz[MX], mxs[MX], cen, cnt;
int sbt[MX], sum[MX], snm;
ll f[MX][MX];

void addeg(int nu, int nv)
{
	nxt[++lnum] = fst[nu];
	fst[nu] = lnum;
	v[lnum] = nv;
}

void input()
{
	int a, b;
	read(n);
	for(int i=1; i<n; i++)
	{
		read(a); read(b);
		addeg(a, b);
		addeg(b, a);
	}
	fac[0] = faci[0] = inv[0] = inv[1] = 1;
	for(int i=2; i<=n; i++) inv[i] = (MOD - MOD/i) * inv[MOD%i] % MOD;
	for(int i=1; i<=n; i++) fac[i] = fac[i-1] * i % MOD, faci[i] = faci[i-1] * inv[i] % MOD;
}

void dfs(int x, int f)
{
	siz[x] = 1;
	for(int i=fst[x]; i; i=nxt[i])
	{
		if(v[i] != f)
		{
			dfs(v[i], x);
			siz[x] += siz[v[i]];
			mxs[x] = max(mxs[x], siz[v[i]]);
		}
	}
	mxs[x] = max(mxs[x], n-siz[x]);
	if(!cen || mxs[x]<mxs[cen]) cen = x, cnt = 1;
	else if(mxs[x] == mxs[cen]) cnt++;
}

void work()
{
	dfs(1, 0);
	assert(cnt <= 2);
	if(cnt > 1) sbt[1] = sbt[2] = n/2, snm = 2;
	else
	{
		for(int i=fst[cen]; i; i=nxt[i])
			if(siz[v[i]] < siz[cen])
				sbt[++snm] = siz[v[i]];
		sbt[++snm] = n-siz[cen];
	}
	sort(sbt+1, sbt+snm+1);
	f[0][0] = 1;
	for(int i=1; i<=snm; i++) sum[i] = sum[i-1] + sbt[i];
	for(int i=1; i<=snm; i++)
	{
		for(int j=0; j<=sum[i]; j++)
		{
			for(int k=0; k<=sbt[i]&&k<=j; k++)
			{
				ll f2 = fac[sbt[i]] * fac[sbt[i]] % MOD;
				ll d2 = faci[sbt[i]-k] * faci[sbt[i]-k] % MOD;
				ll d = faci[k] % MOD;
				f[i][j] = (f[i][j] + f[i-1][j-k] * f2 % MOD *d2 % MOD * d) % MOD;
			}
		}
	}
	ll ans = 0;
	for(int i=0; i<=n; i++)
		if(i & 1) ans = (ans + MOD*MOD - f[snm][i]*fac[n-i]) % MOD;
		else ans = (ans + f[snm][i]*fac[n-i]) % MOD;
	printf("%lld\n", ans);
}
int main()
{
	input();
	work();
	return 0;
}
```