#include<bits/stdc++.h>

using namespace std;

#define int long long

const int   mod = 1e9 + 7;
const int   N   = 5e3 + 1;

void add(int &a,int b)  {
	a += b;
	if(a >= mod)a -= mod;
	if(a <  0)  a += mod;
}
int qpow(int a,int exp) {
	int ans = 1;
	while (exp) {
		if(exp & 1) ans = ans * a % mod;
		a = a * a % mod;  exp >>= 1;
	}
	return  ans;
}

int Fac[N], Inv[N];

int n, c, nCh[N];
vector<int> g[N];

void dfs(int u,int p)   {
	nCh[u] = 1;
	for(int v : g[u])
		if (v != p) {
			dfs(v,u);
			nCh[u] += nCh[v];
		}
}
int Cen(int u,int p)    {
	for(int v : g[u])
		if (v != p && nCh[v] > n / 2)
			return Cen(v,u);
	for(int v : g[u])
		if (v != p && nCh[v] == n - nCh[v]) {
			cout << Fac[n / 2] * Fac[n / 2] % mod;
			exit(0);
		}
	return u;
}

int f[N], r[N];

signed main()   {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n;
	
	Fac[0] = 1;
	for(int i = 1 ; i <= n ; ++i)   Fac[i] = Fac[i - 1] * i % mod;
	Inv[n] = qpow(Fac[n],mod - 2);
	for(int i = n - 1 ; ~i ; --i)   Inv[i] = Inv[i + 1] * (i + 1) % mod;
		
	for(int i = 1 ; i < n ; ++i)    {
		int x, y;   cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	
	dfs(1,0);   c = Cen(1,0);
	dfs(c,0);
	vector<int> vec;
	for(int v : g[c])   vec.push_back(nCh[v]);
	
	int cur = 0;
	f[0] = 1;
	for(int x : vec)    {
		cur += x;
		for(int i = 0 ; i <= cur ; ++i) {
			r[i] = f[i];
			f[i] = 0;
			for(int j = 0 ; j <= min(i,x) ; ++j)    {
				int choose = Fac[x] * Fac[x] % mod;
				    choose = choose * Inv[j] % mod;
				    choose = choose * Inv[x - j] % mod;
				    choose = choose * Inv[x - j] % mod;
				add(f[i],r[i - j] * choose % mod);
			}
		}
	}
	
	int ans = 0, mul = 1;
	
	for(int i = 0 ; i < n ; ++i, mul = -mul)
		add(ans,mul * f[i] * Fac[n - i] % mod);
	
	cout << ans << endl;
}
### Prompt

In CPP, your task is to solve 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>

using namespace std;

#define int long long

const int   mod = 1e9 + 7;
const int   N   = 5e3 + 1;

void add(int &a,int b)  {
	a += b;
	if(a >= mod)a -= mod;
	if(a <  0)  a += mod;
}
int qpow(int a,int exp) {
	int ans = 1;
	while (exp) {
		if(exp & 1) ans = ans * a % mod;
		a = a * a % mod;  exp >>= 1;
	}
	return  ans;
}

int Fac[N], Inv[N];

int n, c, nCh[N];
vector<int> g[N];

void dfs(int u,int p)   {
	nCh[u] = 1;
	for(int v : g[u])
		if (v != p) {
			dfs(v,u);
			nCh[u] += nCh[v];
		}
}
int Cen(int u,int p)    {
	for(int v : g[u])
		if (v != p && nCh[v] > n / 2)
			return Cen(v,u);
	for(int v : g[u])
		if (v != p && nCh[v] == n - nCh[v]) {
			cout << Fac[n / 2] * Fac[n / 2] % mod;
			exit(0);
		}
	return u;
}

int f[N], r[N];

signed main()   {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n;
	
	Fac[0] = 1;
	for(int i = 1 ; i <= n ; ++i)   Fac[i] = Fac[i - 1] * i % mod;
	Inv[n] = qpow(Fac[n],mod - 2);
	for(int i = n - 1 ; ~i ; --i)   Inv[i] = Inv[i + 1] * (i + 1) % mod;
		
	for(int i = 1 ; i < n ; ++i)    {
		int x, y;   cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	
	dfs(1,0);   c = Cen(1,0);
	dfs(c,0);
	vector<int> vec;
	for(int v : g[c])   vec.push_back(nCh[v]);
	
	int cur = 0;
	f[0] = 1;
	for(int x : vec)    {
		cur += x;
		for(int i = 0 ; i <= cur ; ++i) {
			r[i] = f[i];
			f[i] = 0;
			for(int j = 0 ; j <= min(i,x) ; ++j)    {
				int choose = Fac[x] * Fac[x] % mod;
				    choose = choose * Inv[j] % mod;
				    choose = choose * Inv[x - j] % mod;
				    choose = choose * Inv[x - j] % mod;
				add(f[i],r[i - j] * choose % mod);
			}
		}
	}
	
	int ans = 0, mul = 1;
	
	for(int i = 0 ; i < n ; ++i, mul = -mul)
		add(ans,mul * f[i] * Fac[n - i] % mod);
	
	cout << ans << endl;
}
```