#include<bits/stdc++.h>

using namespace std;
typedef long long LL;

#ifdef BTK
#define DEBUG if(1)
#else
#define CIN_ONLY if(1)
struct cww {cww() {CIN_ONLY{ios::sync_with_stdio(false); cin.tie(0);}}
}star;
#define DEBUG if(0)
#endif

#define ALL(v) (v).begin(),(v).end()
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l, T r){bool a = l>r; if (a)l = r; return a;}
template <typename T>inline bool chmax(T &l, T r){bool a = l<r; if (a)l = r; return a;}
template <typename T>istream& operator>>(istream &is, vector<T> &v){for (auto &it : v)is >> it;return is;}

class range {private: struct I { int x; int operator*() { return x; }bool operator!=(I& lhs) { return x<lhs.x; }void operator++() { ++x; } }; I i, n;public:range(int n) :i({ 0 }), n({ n }) {}range(int i, int n) :i({ i }), n({ n }) {}I& begin() { return i; }I& end() { return n; }};

typedef vector<int> V;
typedef vector<V> VV;
int N;
VV g;
int sz[5123];
VV branch;
void dfs(int v = 0, int p = -1) {
	sz[v] = 1;
	branch[v].push_back(N - 1);
	for (int u : g[v]) {
		if (p == u)continue;
		dfs(u, v);
		sz[v] += sz[u];
		branch[v].push_back(sz[u]);
		branch[v].front() -= sz[u];
	}
}
constexpr int mod = 1e9 + 7;
// mを法とするaの逆元
// O(log a)
inline LL invMod(LL a, LL m = mod) {
	LL b = m, u = 1, v = 0;
	while (b) {
		LL t = a / b;
		swap(a -= t * b, b);
		swap(u -= t * v, v);
	}
	return (u % m + m) % m;
}

// 階乗
// O(n)
constexpr int SZ = 112345;
LL fact[SZ];
LL rfact[SZ];
struct fact_ {
	fact_() {
		fact[0] = 1;
		for (int i = 1; i<SZ; i++)
			fact[i] = fact[i - 1] * i%mod;
		rfact[SZ - 1] = invMod(fact[SZ - 1]);
		for (int i = SZ - 1; i>0; i--) {
			rfact[i - 1] = rfact[i] * i%mod;
		}
	}
}fact_init;
// O(1)
LL Comb(LL n, LL k) {
	LL u = fact[n];
	LL d = (rfact[k] * rfact[n - k]) % mod;
	return u * d%mod;
}

//O(1)
LL Perm(LL n, LL k) {
	LL u = fact[n];
	LL d = rfact[n - k] % mod;
	return u * d%mod;
}

LL dp[5123];
LL f(int v) {
	for (int i : range(N)) {
		dp[i] = 0;
	}
	dp[0] = 1;
	int ub = 1;
	for (auto cnt : branch[v]) {
		ub += cnt;
		for (int i = ub - 1; i >= 0; i--) {
			for (int j = 1; j <= min(i, cnt); j++) {
				LL c = Comb(cnt, j) * Perm(cnt, j) % mod;
				dp[i] += dp[i - j] * c %mod;
			}
			dp[i] %= mod;
		}
	}
	LL ret = 0;
	for (int i : range(N)) {
		if (i & 1) {
			ret += mod - dp[i] * fact[N - i] % mod;
		}
		else {
			ret += dp[i] * fact[N - i] % mod;
		}
	}
	return ret % mod;
}

void solve() {
	g = VV(N);
	branch = VV(N);
	for (int i : range(N - 1)) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs();
	if (N % 2==0) {
		for (int v : range(N)) {
			if (sz[v] == N / 2) {
				cout << fact[N / 2] * fact[N / 2] % mod << endl;
				return;
			}
		}
	}
	for (int v : range(N)) {
		bool isCentroid = true;
		for (auto cnt : branch[v])isCentroid &= (cnt <= N / 2);
		if (isCentroid) {
			cout << f(v) << endl;
			return;
		}
	}

}
int main() {
	while (cin >> N) {
		solve();
	}
	return 0;
}

### Prompt

Develop a solution in cpp 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;

#ifdef BTK
#define DEBUG if(1)
#else
#define CIN_ONLY if(1)
struct cww {cww() {CIN_ONLY{ios::sync_with_stdio(false); cin.tie(0);}}
}star;
#define DEBUG if(0)
#endif

#define ALL(v) (v).begin(),(v).end()
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l, T r){bool a = l>r; if (a)l = r; return a;}
template <typename T>inline bool chmax(T &l, T r){bool a = l<r; if (a)l = r; return a;}
template <typename T>istream& operator>>(istream &is, vector<T> &v){for (auto &it : v)is >> it;return is;}

class range {private: struct I { int x; int operator*() { return x; }bool operator!=(I& lhs) { return x<lhs.x; }void operator++() { ++x; } }; I i, n;public:range(int n) :i({ 0 }), n({ n }) {}range(int i, int n) :i({ i }), n({ n }) {}I& begin() { return i; }I& end() { return n; }};

typedef vector<int> V;
typedef vector<V> VV;
int N;
VV g;
int sz[5123];
VV branch;
void dfs(int v = 0, int p = -1) {
	sz[v] = 1;
	branch[v].push_back(N - 1);
	for (int u : g[v]) {
		if (p == u)continue;
		dfs(u, v);
		sz[v] += sz[u];
		branch[v].push_back(sz[u]);
		branch[v].front() -= sz[u];
	}
}
constexpr int mod = 1e9 + 7;
// mを法とするaの逆元
// O(log a)
inline LL invMod(LL a, LL m = mod) {
	LL b = m, u = 1, v = 0;
	while (b) {
		LL t = a / b;
		swap(a -= t * b, b);
		swap(u -= t * v, v);
	}
	return (u % m + m) % m;
}

// 階乗
// O(n)
constexpr int SZ = 112345;
LL fact[SZ];
LL rfact[SZ];
struct fact_ {
	fact_() {
		fact[0] = 1;
		for (int i = 1; i<SZ; i++)
			fact[i] = fact[i - 1] * i%mod;
		rfact[SZ - 1] = invMod(fact[SZ - 1]);
		for (int i = SZ - 1; i>0; i--) {
			rfact[i - 1] = rfact[i] * i%mod;
		}
	}
}fact_init;
// O(1)
LL Comb(LL n, LL k) {
	LL u = fact[n];
	LL d = (rfact[k] * rfact[n - k]) % mod;
	return u * d%mod;
}

//O(1)
LL Perm(LL n, LL k) {
	LL u = fact[n];
	LL d = rfact[n - k] % mod;
	return u * d%mod;
}

LL dp[5123];
LL f(int v) {
	for (int i : range(N)) {
		dp[i] = 0;
	}
	dp[0] = 1;
	int ub = 1;
	for (auto cnt : branch[v]) {
		ub += cnt;
		for (int i = ub - 1; i >= 0; i--) {
			for (int j = 1; j <= min(i, cnt); j++) {
				LL c = Comb(cnt, j) * Perm(cnt, j) % mod;
				dp[i] += dp[i - j] * c %mod;
			}
			dp[i] %= mod;
		}
	}
	LL ret = 0;
	for (int i : range(N)) {
		if (i & 1) {
			ret += mod - dp[i] * fact[N - i] % mod;
		}
		else {
			ret += dp[i] * fact[N - i] % mod;
		}
	}
	return ret % mod;
}

void solve() {
	g = VV(N);
	branch = VV(N);
	for (int i : range(N - 1)) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs();
	if (N % 2==0) {
		for (int v : range(N)) {
			if (sz[v] == N / 2) {
				cout << fact[N / 2] * fact[N / 2] % mod << endl;
				return;
			}
		}
	}
	for (int v : range(N)) {
		bool isCentroid = true;
		for (auto cnt : branch[v])isCentroid &= (cnt <= N / 2);
		if (isCentroid) {
			cout << f(v) << endl;
			return;
		}
	}

}
int main() {
	while (cin >> N) {
		solve();
	}
	return 0;
}

```