#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 5005, mod = 1e9+7;

ll n, chi[N], fac[N] = {1}, fi[N] = {1}, dt[N][N];

vector<ll> adj[N], a;

void calc (ll C, ll P) {
	chi[C] = 1;
	for(auto &T : adj[C]) {
		if(T == P) continue;
		calc(T, C);
		chi[C] += chi[T];
	}
}

ll fcen (ll C, ll P) {
	ll mx = 0, i;
	for(auto &T : adj[C]) {
		if(T == P) continue;
		if(mx < chi[T]) {
			mx = chi[T];
			i = T;
		}
	}
	if(mx <= n/2) return C;
	return fcen(i, C);
}

ll pw (ll X, ll Y) {
	if(!Y) return 1;
	ll R = pw(X, Y/2);
	R = R * R % mod;
	if(Y&1) R = R * X % mod;
	return R;
}

ll cmb (ll X, ll Y) {
	if(X < Y || Y < 0) return 0;
	return fac[X] * fi[Y] % mod * fi[X-Y] % mod;
}

int main()
{
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++) {
		fac[i] = fac[i-1] * i % mod;
		fi[i] = pw(fac[i], mod-2);
	}
	for(ll i=1;i<n;i++) {
		ll A, B;
		scanf("%lld%lld",&A,&B);
		adj[A].push_back(B);
		adj[B].push_back(A);
	}
	calc(1, 0);
	ll C = fcen(1, 0);
	for(auto &T : adj[C]) {
		if(chi[T] < chi[C]) a.push_back(chi[T]);
	}
	a.push_back(chi[1] - chi[C]);
	a.push_back(1);
	ll S = a[0], Z = a.size();
	dt[0][a[0]] = fac[a[0]];
	for(ll i=1;i<Z;i++) {
		for(ll j=0;j<a[i];j++) {
			for(ll k=0;k<=n;k++) {
				dt[i+j][k] = dt[i+j-1][k] * (S-j-k) + dt[i+j-1][k+1] * (k+1);
				dt[i+j][k] %= mod;
			}
		}
		for(ll k=n;k>=0;k--) {
			if(k >= a[i]-1) dt[i][k] = dt[i][k-a[i]+1] * a[i] % mod * fac[a[i]] % mod;
			else dt[i][k] = 0;
			if(k >= a[i]) dt[i][k] = (dt[i][k] + dt[i-1][k-a[i]] * fac[a[i]]) % mod;
		}
		for(ll j=1;j<a[i];j++) {
			for(ll k=n;k>=a[i]-j-1;k--) {
				dt[i][k] += dt[i+j][k-a[i]+j+1] * cmb(a[i], j+1) % mod * fac[a[i]] % mod * fi[j+1];
				dt[i][k] %= mod;
			}
		}
		S += a[i];
	}
	printf("%lld\n",(dt[Z-2][0]+dt[Z-1][0])%mod);
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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>
using namespace std;
typedef long long ll;
const ll N = 5005, mod = 1e9+7;

ll n, chi[N], fac[N] = {1}, fi[N] = {1}, dt[N][N];

vector<ll> adj[N], a;

void calc (ll C, ll P) {
	chi[C] = 1;
	for(auto &T : adj[C]) {
		if(T == P) continue;
		calc(T, C);
		chi[C] += chi[T];
	}
}

ll fcen (ll C, ll P) {
	ll mx = 0, i;
	for(auto &T : adj[C]) {
		if(T == P) continue;
		if(mx < chi[T]) {
			mx = chi[T];
			i = T;
		}
	}
	if(mx <= n/2) return C;
	return fcen(i, C);
}

ll pw (ll X, ll Y) {
	if(!Y) return 1;
	ll R = pw(X, Y/2);
	R = R * R % mod;
	if(Y&1) R = R * X % mod;
	return R;
}

ll cmb (ll X, ll Y) {
	if(X < Y || Y < 0) return 0;
	return fac[X] * fi[Y] % mod * fi[X-Y] % mod;
}

int main()
{
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++) {
		fac[i] = fac[i-1] * i % mod;
		fi[i] = pw(fac[i], mod-2);
	}
	for(ll i=1;i<n;i++) {
		ll A, B;
		scanf("%lld%lld",&A,&B);
		adj[A].push_back(B);
		adj[B].push_back(A);
	}
	calc(1, 0);
	ll C = fcen(1, 0);
	for(auto &T : adj[C]) {
		if(chi[T] < chi[C]) a.push_back(chi[T]);
	}
	a.push_back(chi[1] - chi[C]);
	a.push_back(1);
	ll S = a[0], Z = a.size();
	dt[0][a[0]] = fac[a[0]];
	for(ll i=1;i<Z;i++) {
		for(ll j=0;j<a[i];j++) {
			for(ll k=0;k<=n;k++) {
				dt[i+j][k] = dt[i+j-1][k] * (S-j-k) + dt[i+j-1][k+1] * (k+1);
				dt[i+j][k] %= mod;
			}
		}
		for(ll k=n;k>=0;k--) {
			if(k >= a[i]-1) dt[i][k] = dt[i][k-a[i]+1] * a[i] % mod * fac[a[i]] % mod;
			else dt[i][k] = 0;
			if(k >= a[i]) dt[i][k] = (dt[i][k] + dt[i-1][k-a[i]] * fac[a[i]]) % mod;
		}
		for(ll j=1;j<a[i];j++) {
			for(ll k=n;k>=a[i]-j-1;k--) {
				dt[i][k] += dt[i+j][k-a[i]+j+1] * cmb(a[i], j+1) % mod * fac[a[i]] % mod * fi[j+1];
				dt[i][k] %= mod;
			}
		}
		S += a[i];
	}
	printf("%lld\n",(dt[Z-2][0]+dt[Z-1][0])%mod);
}

```