#include <bits/stdc++.h>
#define rep(i,  x,  y) for(int i = x; i <= y; i ++)
#define ll long long
#define X first
#define Y second
#define ls rt << 1
#define rs rt << 1 | 1
#define INF 0x3f3f3f3f
#define mod 1000000007
using namespace std;
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
const int N = 10010;
struct edge
{
	int v, next;
}E[N << 1];
inline ll qpow(ll bas,int pw)
{
	ll ret = 1;
	while(pw)
	{
		if(pw & 1) ret = 1ll * ret * bas % mod;
		bas = 1ll * bas * bas % mod;
		pw >>= 1;
	}
	return ret;
}
ll n,ee,head[N],p1,s1,p2,s2;
ll size[N],jc[N],ny[N],fa[N];
ll bs[N],tot,F[N],G[N];
inline void addedge(int u,int v)
{
	E[++ ee].v = v;
	E[ee].next = head[u];
	head[u] = ee;
}
inline void dfs(int rt)
{
	size[rt] = 1;
	ll mx = 0;
	for(int i = head[rt]; i; i = E[i].next)
	{
		if(E[i].v == fa[rt]) continue;
		fa[E[i].v] = rt;
		dfs(E[i].v);
		size[rt] += size[E[i].v];
		mx = max(mx, size[E[i].v]);
	}
	ll sd = max(mx, n - size[rt]), pd = rt;
	if(sd < s1) swap(sd, s1), swap(pd, p1);
	if(sd < s2) swap(sd, s2), swap(pd, p2);
}
inline void Add(ll &x,ll y)
{
	x += y;
	if(x >= mod) x -= mod;
	if(x < 0) x += mod;
}
inline ll C(int n,int m)
{
	return 1ll * jc[n] * ny[m] % mod * ny[n - m] % mod;
}
int main()
{
	jc[0] = ny[0] = 1;
	rep(i, 1, 5000) jc[i] = 1ll * jc[i - 1] * i % mod;
	ny[5000] = qpow(jc[5000], mod - 2);
	for(int i = 4999; i >= 1; i --) ny[i] = 1ll * ny[i + 1] * (i + 1) % mod;
	n = read();
	s1 = s2 = n + 1;
	rep(i, 1, n - 1)
	{
		int u = read(), v = read();
		addedge(u, v);
		addedge(v, u);
	}
	dfs(1);
	if(!(s1 ^ s2)) {cout << 1ll * jc[n / 2] * jc[n / 2] % mod << endl; return 0;}
	else
	{
		for(int i = head[p1]; i; i = E[i].next)
		{
			if(E[i].v == fa[p1]) continue;
			bs[++ tot] = size[E[i].v];
		}
		bs[++ tot] = n - size[p1];
		F[0] = 1;
		rep(i, 1, tot)
		{
			rep(j, 0, n - 1) G[j] = F[j];
			rep(j, 1, bs[i])
				for(int k = n - 1; k >= j; k --)
					if(F[k - j])
						Add(G[k], 1ll * F[k - j] * jc[bs[i]] % mod * ny[bs[i] - j] % mod * C(bs[i], j) % mod);
			rep(j, 0, n - 1) F[j] = G[j];
		}
		ll Ans = jc[n];
		for(int i = 1, f = -1; i <= n - 1; i ++, f *= -1)
			Add(Ans, f * F[i] * jc[n - i] % mod);
		cout << Ans << endl;
	}
	return 0;
}

### Prompt

Please create a solution in cpp 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 <bits/stdc++.h>
#define rep(i,  x,  y) for(int i = x; i <= y; i ++)
#define ll long long
#define X first
#define Y second
#define ls rt << 1
#define rs rt << 1 | 1
#define INF 0x3f3f3f3f
#define mod 1000000007
using namespace std;
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
const int N = 10010;
struct edge
{
	int v, next;
}E[N << 1];
inline ll qpow(ll bas,int pw)
{
	ll ret = 1;
	while(pw)
	{
		if(pw & 1) ret = 1ll * ret * bas % mod;
		bas = 1ll * bas * bas % mod;
		pw >>= 1;
	}
	return ret;
}
ll n,ee,head[N],p1,s1,p2,s2;
ll size[N],jc[N],ny[N],fa[N];
ll bs[N],tot,F[N],G[N];
inline void addedge(int u,int v)
{
	E[++ ee].v = v;
	E[ee].next = head[u];
	head[u] = ee;
}
inline void dfs(int rt)
{
	size[rt] = 1;
	ll mx = 0;
	for(int i = head[rt]; i; i = E[i].next)
	{
		if(E[i].v == fa[rt]) continue;
		fa[E[i].v] = rt;
		dfs(E[i].v);
		size[rt] += size[E[i].v];
		mx = max(mx, size[E[i].v]);
	}
	ll sd = max(mx, n - size[rt]), pd = rt;
	if(sd < s1) swap(sd, s1), swap(pd, p1);
	if(sd < s2) swap(sd, s2), swap(pd, p2);
}
inline void Add(ll &x,ll y)
{
	x += y;
	if(x >= mod) x -= mod;
	if(x < 0) x += mod;
}
inline ll C(int n,int m)
{
	return 1ll * jc[n] * ny[m] % mod * ny[n - m] % mod;
}
int main()
{
	jc[0] = ny[0] = 1;
	rep(i, 1, 5000) jc[i] = 1ll * jc[i - 1] * i % mod;
	ny[5000] = qpow(jc[5000], mod - 2);
	for(int i = 4999; i >= 1; i --) ny[i] = 1ll * ny[i + 1] * (i + 1) % mod;
	n = read();
	s1 = s2 = n + 1;
	rep(i, 1, n - 1)
	{
		int u = read(), v = read();
		addedge(u, v);
		addedge(v, u);
	}
	dfs(1);
	if(!(s1 ^ s2)) {cout << 1ll * jc[n / 2] * jc[n / 2] % mod << endl; return 0;}
	else
	{
		for(int i = head[p1]; i; i = E[i].next)
		{
			if(E[i].v == fa[p1]) continue;
			bs[++ tot] = size[E[i].v];
		}
		bs[++ tot] = n - size[p1];
		F[0] = 1;
		rep(i, 1, tot)
		{
			rep(j, 0, n - 1) G[j] = F[j];
			rep(j, 1, bs[i])
				for(int k = n - 1; k >= j; k --)
					if(F[k - j])
						Add(G[k], 1ll * F[k - j] * jc[bs[i]] % mod * ny[bs[i] - j] % mod * C(bs[i], j) % mod);
			rep(j, 0, n - 1) F[j] = G[j];
		}
		ll Ans = jc[n];
		for(int i = 1, f = -1; i <= n - 1; i ++, f *= -1)
			Add(Ans, f * F[i] * jc[n - i] % mod);
		cout << Ans << endl;
	}
	return 0;
}

```