#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l), i##end = (r);i <= i##end;++i)
using std::cin; using std::cout;
const int maxn = 5005;
typedef long long ll;
const int mod = 1e9 + 7;
inline ll pow(ll a,int b,int ans = 1) {
	for(;b;b >>= 1,a = a * a % mod) if(b & 1)
		ans = ans * a % mod;
	return ans;
}
inline ll inverse(int x){ return pow(x, mod - 2); }
int n;
struct T {
	int to, nxt;
} way[maxn << 1];
int h[maxn], num;
int fac[maxn], ifac[maxn], inv[maxn];
inline void link(int x,int y) {
	way[++num] = {y, h[x]}, h[x] = num;
	way[++num] = {x, h[y]}, h[y] = num;
}
int size[maxn];
int root, min;
inline void dfs0(int x,int fa = 0) {
	size[x] = 1;
	for(int i = h[x];i;i = way[i].nxt) if(way[i].to != fa) {
		dfs0(way[i].to, x);
		size[x] += size[way[i].to];
	}
}
inline void dfs1(int x,int fa = 0) {
	int max = n - size[x];
	for(int i = h[x];i;i = way[i].nxt) if(way[i].to != fa) {
		dfs1(way[i].to, x);
		max = std::max(max, size[way[i].to]);
	}
	if(max < min) {
		min = max;
		root = x;
	}
}
int g[maxn][maxn];
inline int C(int x,int y) {
	return (ll) fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}
inline int A(int x,int y) {
	return (ll) fac[x] * ifac[x - y] % mod;
}
inline int solve(std::vector<int> v) {
	g[0][0] = 1; int s = 0, c = 0;
	for(int i : v) {
		++ c;
		rep(k, 0, s) rep(j, 0, i) {
			g[c][k + j] = (g[c][k + j] + (ll) g[c - 1][k] * C(i, j) % mod * A(i, j)) % mod;
		}
		s += i;
	}
	int ans = 0;
	rep(i, 0, n) {
		ans = (ans + ll(i & 1 ? mod - g[c][i] : g[c][i]) * fac[n - i]) % mod;
	}
	return ans;
}
int main() {
	fac[0] = ifac[0] = fac[1] = ifac[1] = inv[1] = 1;
	for(int i = 2;i < maxn;++i) {
		inv[i] = ll(mod - mod / i) * inv[mod % i] % mod;
		fac[i] = (ll) fac[i - 1] * i % mod;
		ifac[i] = (ll) ifac[i - 1] * inv[i] % mod;
	}
	std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	rep(i, 2, n) {
		int x, y;
		cin >> x >> y;
		link(x, y);
	}
	dfs0(1);
	min = 1e9;
	dfs1(1);
	if(min + min == n) {
		cout << (ll) fac[min] * fac[min] % mod << '\n';
		return 0;
	}
	std::vector<int> v;
	for(int i = h[root];i;i = way[i].nxt) if(size[way[i].to] < size[root])
		v.push_back(size[way[i].to]);
	if(root != 1) v.push_back(n - size[root]);
	cout << solve(v) << '\n';
}

### 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<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l), i##end = (r);i <= i##end;++i)
using std::cin; using std::cout;
const int maxn = 5005;
typedef long long ll;
const int mod = 1e9 + 7;
inline ll pow(ll a,int b,int ans = 1) {
	for(;b;b >>= 1,a = a * a % mod) if(b & 1)
		ans = ans * a % mod;
	return ans;
}
inline ll inverse(int x){ return pow(x, mod - 2); }
int n;
struct T {
	int to, nxt;
} way[maxn << 1];
int h[maxn], num;
int fac[maxn], ifac[maxn], inv[maxn];
inline void link(int x,int y) {
	way[++num] = {y, h[x]}, h[x] = num;
	way[++num] = {x, h[y]}, h[y] = num;
}
int size[maxn];
int root, min;
inline void dfs0(int x,int fa = 0) {
	size[x] = 1;
	for(int i = h[x];i;i = way[i].nxt) if(way[i].to != fa) {
		dfs0(way[i].to, x);
		size[x] += size[way[i].to];
	}
}
inline void dfs1(int x,int fa = 0) {
	int max = n - size[x];
	for(int i = h[x];i;i = way[i].nxt) if(way[i].to != fa) {
		dfs1(way[i].to, x);
		max = std::max(max, size[way[i].to]);
	}
	if(max < min) {
		min = max;
		root = x;
	}
}
int g[maxn][maxn];
inline int C(int x,int y) {
	return (ll) fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}
inline int A(int x,int y) {
	return (ll) fac[x] * ifac[x - y] % mod;
}
inline int solve(std::vector<int> v) {
	g[0][0] = 1; int s = 0, c = 0;
	for(int i : v) {
		++ c;
		rep(k, 0, s) rep(j, 0, i) {
			g[c][k + j] = (g[c][k + j] + (ll) g[c - 1][k] * C(i, j) % mod * A(i, j)) % mod;
		}
		s += i;
	}
	int ans = 0;
	rep(i, 0, n) {
		ans = (ans + ll(i & 1 ? mod - g[c][i] : g[c][i]) * fac[n - i]) % mod;
	}
	return ans;
}
int main() {
	fac[0] = ifac[0] = fac[1] = ifac[1] = inv[1] = 1;
	for(int i = 2;i < maxn;++i) {
		inv[i] = ll(mod - mod / i) * inv[mod % i] % mod;
		fac[i] = (ll) fac[i - 1] * i % mod;
		ifac[i] = (ll) ifac[i - 1] * inv[i] % mod;
	}
	std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	rep(i, 2, n) {
		int x, y;
		cin >> x >> y;
		link(x, y);
	}
	dfs0(1);
	min = 1e9;
	dfs1(1);
	if(min + min == n) {
		cout << (ll) fac[min] * fac[min] % mod << '\n';
		return 0;
	}
	std::vector<int> v;
	for(int i = h[root];i;i = way[i].nxt) if(size[way[i].to] < size[root])
		v.push_back(size[way[i].to]);
	if(root != 1) v.push_back(n - size[root]);
	cout << solve(v) << '\n';
}

```