#include <bits/stdc++.h>

using namespace std;

#ifdef SG
	#include <debug.h>
#else
	#define show(...)
	#define debug(...)
	#define deepen(...)
	#define timer(...)
#endif

#define ARG4(_1,_2,_3,_4,...) _4

#define forn3(i,l,r) for (int i = int(l); i < int(r); ++i)
#define forn2(i,n) forn3 (i, 0, n)
#define forn(...) ARG4(__VA_ARGS__, forn3, forn2) (__VA_ARGS__)

#define ford3(i,l,r) for (int i = int(r) - 1; i >= int(l); --i)
#define ford2(i,n) ford3 (i, 0, n)
#define ford(...) ARG4(__VA_ARGS__, ford3, ford2) (__VA_ARGS__)

#define ve vector
#define pa pair
#define tu tuple
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define fs first
#define sc second
#define all(a) (a).begin(), (a).end()
#define sz(a) ((int)(a).size())

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef unsigned char uc;
typedef pa<int, int> pii;
typedef pa<int, ll> pil;
typedef pa<ll, int> pli;
typedef pa<ll, ll> pll;
typedef ve<int> vi;

const ld pi = 3.1415926535897932384626433832795l;

template<typename T> inline auto sqr (T x) -> decltype(x * x) {return x * x;}
template<typename T1, typename T2> inline bool umx (T1& a, T2 b) {if (a < b) {a = b; return 1;} return 0;}
template<typename T1, typename T2> inline bool umn (T1& a, T2 b) {if (b < a) {a = b; return 1;} return 0;}

const int N = 5010;

ll fact[N];
ll obrfact[N];
vi a[N];
int pr[N];
bool use[N];
int sz[N];

int dfs(int v) {
	sz[v] = 1;
	use[v] = 1;
	forn(i, sz(a[v])) {
		if (!use[a[v][i]]) {
			pr[a[v][i]] = v;
		 	sz[v] += dfs(a[v][i]);
		}
	}
	return sz[v];
}

const ll mod = 1000000007;
int d[2][N];

ll get_st(ll a, int st) {
	ll res = 1;
	while (st) {
		if (st & 1) {
			(res *= a) %= mod;
		}
		(a *= a) %= mod;
		st >>= 1;
	}
	return res;
}

int n;

ll calc(vi& a, bool full) {
	memset(d, 0, sizeof(d));
	d[0][0] = 1;	
	forn(i, sz(a)) {
		int i0 = i & 1, i1 = (i0 ^ 1);
		forn(j, N) {
			if (!d[i0][j])
				continue;
			forn(k, a[i] + 1) {
				d[i1][j + k] += d[i0][j] * fact[a[i]] % mod * fact[a[i]] % mod * obrfact[a[i] - k] % mod * obrfact[a[i] - k] % mod * obrfact[k] % mod;
				(d[i1][j + k] %= mod);
			}
			d[i0][j] = 0;
		}
	}
	debug(d[sz(a) & 1], d[sz(a) & 1] + 10);
	ll res = 0;
	forn(i, n + full) {
		if (!(i & 1)) {
			res += (d[sz(a) & 1][i]) * fact[n - 1 - i + full] % mod;
        } else {
            res = res - (d[sz(a) & 1][i]) * fact[n - 1 - i + full] % mod + mod;
        }
        res %= mod;
	}
	return res;
}

int main () {
	//std::ios::sync_with_stdio(false);
	cout.setf(ios::showpoint | ios::fixed);
	cout.precision(20);
#ifdef SG
	freopen((problemname + ".in").c_str(), "r", stdin);
//	freopen((problemname + ".out").c_str(), "w", stdout);
#endif
	cin >> n;
	forn(i, n - 1) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		a[u].pb(v);
		a[v].pb(u);
	}
	fact[0] = obrfact[0] = 1;
	forn(i, 1, N) {
		(fact[i] = fact[i - 1] * i) %= mod;    
		obrfact[i] = get_st(fact[i], mod - 2);    
    }
    memset(pr, -1, sizeof(pr));
	dfs(0);
	int st = 0;
	debug(sz, sz + n);

	while(1) {
		int maxi = -1, maxx = -1;
		debug(st);
		forn(i, sz(a[st])) {
		 	int to = a[st][i];
		 	int teksz = sz[to];
		 	if (pr[st] == to) {
				teksz = n - sz[st];		 		
		 	}
		 	if (umx(maxx, teksz)) {
            	maxi = to;
            }
		}
		if (maxx == n / 2 && !(n & 1)) {
			cout << (fact[n / 2] * fact[n / 2]) % mod << endl;
			return 0;		
		}
		if (maxx > n / 2) {
			st = maxi;
		} else {
	    	break;
		}
	}
	pr[st] = -1;
	memset(use, 0, sizeof(use));
	dfs(st);
	vi ord;
	forn(i, sz(a[st])) {
		ord.pb(sz[a[st][i]]);
	}
	ll res = calc(ord, 0);
	ord.pb(1);
	debug(res);
	(res += calc(ord, 1)) %= mod;
	cout << res << endl;

	return 0;
}
### Prompt

Please create a solution in Cpp 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>

using namespace std;

#ifdef SG
	#include <debug.h>
#else
	#define show(...)
	#define debug(...)
	#define deepen(...)
	#define timer(...)
#endif

#define ARG4(_1,_2,_3,_4,...) _4

#define forn3(i,l,r) for (int i = int(l); i < int(r); ++i)
#define forn2(i,n) forn3 (i, 0, n)
#define forn(...) ARG4(__VA_ARGS__, forn3, forn2) (__VA_ARGS__)

#define ford3(i,l,r) for (int i = int(r) - 1; i >= int(l); --i)
#define ford2(i,n) ford3 (i, 0, n)
#define ford(...) ARG4(__VA_ARGS__, ford3, ford2) (__VA_ARGS__)

#define ve vector
#define pa pair
#define tu tuple
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define fs first
#define sc second
#define all(a) (a).begin(), (a).end()
#define sz(a) ((int)(a).size())

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef unsigned char uc;
typedef pa<int, int> pii;
typedef pa<int, ll> pil;
typedef pa<ll, int> pli;
typedef pa<ll, ll> pll;
typedef ve<int> vi;

const ld pi = 3.1415926535897932384626433832795l;

template<typename T> inline auto sqr (T x) -> decltype(x * x) {return x * x;}
template<typename T1, typename T2> inline bool umx (T1& a, T2 b) {if (a < b) {a = b; return 1;} return 0;}
template<typename T1, typename T2> inline bool umn (T1& a, T2 b) {if (b < a) {a = b; return 1;} return 0;}

const int N = 5010;

ll fact[N];
ll obrfact[N];
vi a[N];
int pr[N];
bool use[N];
int sz[N];

int dfs(int v) {
	sz[v] = 1;
	use[v] = 1;
	forn(i, sz(a[v])) {
		if (!use[a[v][i]]) {
			pr[a[v][i]] = v;
		 	sz[v] += dfs(a[v][i]);
		}
	}
	return sz[v];
}

const ll mod = 1000000007;
int d[2][N];

ll get_st(ll a, int st) {
	ll res = 1;
	while (st) {
		if (st & 1) {
			(res *= a) %= mod;
		}
		(a *= a) %= mod;
		st >>= 1;
	}
	return res;
}

int n;

ll calc(vi& a, bool full) {
	memset(d, 0, sizeof(d));
	d[0][0] = 1;	
	forn(i, sz(a)) {
		int i0 = i & 1, i1 = (i0 ^ 1);
		forn(j, N) {
			if (!d[i0][j])
				continue;
			forn(k, a[i] + 1) {
				d[i1][j + k] += d[i0][j] * fact[a[i]] % mod * fact[a[i]] % mod * obrfact[a[i] - k] % mod * obrfact[a[i] - k] % mod * obrfact[k] % mod;
				(d[i1][j + k] %= mod);
			}
			d[i0][j] = 0;
		}
	}
	debug(d[sz(a) & 1], d[sz(a) & 1] + 10);
	ll res = 0;
	forn(i, n + full) {
		if (!(i & 1)) {
			res += (d[sz(a) & 1][i]) * fact[n - 1 - i + full] % mod;
        } else {
            res = res - (d[sz(a) & 1][i]) * fact[n - 1 - i + full] % mod + mod;
        }
        res %= mod;
	}
	return res;
}

int main () {
	//std::ios::sync_with_stdio(false);
	cout.setf(ios::showpoint | ios::fixed);
	cout.precision(20);
#ifdef SG
	freopen((problemname + ".in").c_str(), "r", stdin);
//	freopen((problemname + ".out").c_str(), "w", stdout);
#endif
	cin >> n;
	forn(i, n - 1) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		a[u].pb(v);
		a[v].pb(u);
	}
	fact[0] = obrfact[0] = 1;
	forn(i, 1, N) {
		(fact[i] = fact[i - 1] * i) %= mod;    
		obrfact[i] = get_st(fact[i], mod - 2);    
    }
    memset(pr, -1, sizeof(pr));
	dfs(0);
	int st = 0;
	debug(sz, sz + n);

	while(1) {
		int maxi = -1, maxx = -1;
		debug(st);
		forn(i, sz(a[st])) {
		 	int to = a[st][i];
		 	int teksz = sz[to];
		 	if (pr[st] == to) {
				teksz = n - sz[st];		 		
		 	}
		 	if (umx(maxx, teksz)) {
            	maxi = to;
            }
		}
		if (maxx == n / 2 && !(n & 1)) {
			cout << (fact[n / 2] * fact[n / 2]) % mod << endl;
			return 0;		
		}
		if (maxx > n / 2) {
			st = maxi;
		} else {
	    	break;
		}
	}
	pr[st] = -1;
	memset(use, 0, sizeof(use));
	dfs(st);
	vi ord;
	forn(i, sz(a[st])) {
		ord.pb(sz[a[st][i]]);
	}
	ll res = calc(ord, 0);
	ord.pb(1);
	debug(res);
	(res += calc(ord, 1)) %= mod;
	cout << res << endl;

	return 0;
}
```