#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-3;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
int n;
vector<int> G[5001];
vector<int> g;
bool used[5001];
int cnt[5001];
int dfs(int id) {
	used[id] = true;
	int res = 1;
	bool isg = true;
	rep(j, G[id].size()) {
		int to = G[id][j];
		if (used[to])continue;
		int subres = dfs(to);
		res += subres; if (subres > n / 2)isg = false;
	}
	if (n - res > n / 2)isg = false;
	if (isg)g.push_back(id);
	return cnt[id]=res;
}
ll p[5001];
ll pas[5001][5001];
void init() {
	p[0] = 1;
	rep1(i, 5000) {
		p[i] = p[i - 1] * i%mod;
	}
	rep(i, 5001) {
		rep(j, 5001) {
			if (i == 0 || j == 0)pas[i][j] = 1;
			else pas[i][j] = (pas[i][j - 1] + pas[i - 1][j]) % mod;
		}
	}
}
ll dp[5001][5001]; int sz;
int main() {
	init();
	cin >> n;
	rep(i, n - 1) {
		int a, b; cin >> a >> b; a--; b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	dfs(0);
	if (g.size() == 2) {
		cout << p[n / 2] * p[n / 2] % mod << endl;
	}
	else {
		fill(used, used + n, false);
		dfs(g[0]);
		vector<int> v;
		rep(i, G[g[0]].size()) {
			v.push_back(cnt[G[g[0]][i]]);
		}
		sz = 1; dp[0][0] = 1;
		rep(i, v.size()) {
			rep(j, v[i]+1) {
				rep(k, sz) {
					dp[i + 1][j + k] += dp[i][k] * pas[v[i] - j][j] % mod*pas[v[i] - j][j] % mod*p[j]%mod;
					dp[i + 1][j + k] %= mod;
				}
			}
			sz += v[i];
		}
		ll ans = 0;
		rep(i, sz + 1) {
			ll csum = dp[v.size()][i];
			csum = csum * p[sz - i] % mod;
			if (i % 2)csum = (-csum + mod) % mod;
			(ans += csum) %= mod;
		}
		cout << ans << endl;
	}
	return 0;
}

### Prompt

Create a solution in CPP for 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<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-3;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
int n;
vector<int> G[5001];
vector<int> g;
bool used[5001];
int cnt[5001];
int dfs(int id) {
	used[id] = true;
	int res = 1;
	bool isg = true;
	rep(j, G[id].size()) {
		int to = G[id][j];
		if (used[to])continue;
		int subres = dfs(to);
		res += subres; if (subres > n / 2)isg = false;
	}
	if (n - res > n / 2)isg = false;
	if (isg)g.push_back(id);
	return cnt[id]=res;
}
ll p[5001];
ll pas[5001][5001];
void init() {
	p[0] = 1;
	rep1(i, 5000) {
		p[i] = p[i - 1] * i%mod;
	}
	rep(i, 5001) {
		rep(j, 5001) {
			if (i == 0 || j == 0)pas[i][j] = 1;
			else pas[i][j] = (pas[i][j - 1] + pas[i - 1][j]) % mod;
		}
	}
}
ll dp[5001][5001]; int sz;
int main() {
	init();
	cin >> n;
	rep(i, n - 1) {
		int a, b; cin >> a >> b; a--; b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	dfs(0);
	if (g.size() == 2) {
		cout << p[n / 2] * p[n / 2] % mod << endl;
	}
	else {
		fill(used, used + n, false);
		dfs(g[0]);
		vector<int> v;
		rep(i, G[g[0]].size()) {
			v.push_back(cnt[G[g[0]][i]]);
		}
		sz = 1; dp[0][0] = 1;
		rep(i, v.size()) {
			rep(j, v[i]+1) {
				rep(k, sz) {
					dp[i + 1][j + k] += dp[i][k] * pas[v[i] - j][j] % mod*pas[v[i] - j][j] % mod*p[j]%mod;
					dp[i + 1][j + k] %= mod;
				}
			}
			sz += v[i];
		}
		ll ans = 0;
		rep(i, sz + 1) {
			ll csum = dp[v.size()][i];
			csum = csum * p[sz - i] % mod;
			if (i % 2)csum = (-csum + mod) % mod;
			(ans += csum) %= mod;
		}
		cout << ans << endl;
	}
	return 0;
}

```