#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<deque>
#include<functional>
#include<ctime>
#include<cassert>
#include<cstring>
using namespace std;

#define sz(x) (int)(x.size())
#define fi(a,b) for(int i=a;i<b;++i)
#define fj(a,b) for(int j=a;j<b;++j)
#define fo(a,b) for(int o=a;o<b;++o)
#define fdi(a,b) for(int i=a-1;i>=b;--i)
#define fdj(a,b) for(int j=a-1;j>=b;--j)
#define fdo(a,b) for(int o=a-1;o>=b;--o)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef double ld;
typedef vector<int> vi;

template<class T> bool uin(T &a, T b){ return (a > b ? a = b, true : false); }
template<class T> bool uax(T &a, T b){ return (a < b ? a = b, true : false); }

/////////////////////////////////

int const MOD = 1e9 + 7;
int const N = 5e3 + 41;

int f[N], invf[N], invn[N];
int n;
vi e[N];
int d[N][N];

void add(int &a, int b){
	a += b;
	while(a >= MOD) a -= MOD;
	while(a < 0) a += MOD;
}

int mul(int a, int b){
	return (ll) a * b % MOD;
}

int q[N];
vi c;

void dfs(int x, int p = -1){
	int mq = 0;
	q[x] = 1;
	for(int y : e[x]){
		if(y == p) continue;
		dfs(y, x);
		q[x] += q[y];
		uax(mq, q[y]);
	}
	uax(mq, n-q[x]);
	if(mq * 2 <= n) c.pb(x);
}

int getc(int n, int k){
	int res = f[n];
	res = mul(res, invf[k]);
	res = mul(res, invf[n-k]);
	return res;
}

int main(){
#ifdef LOCAL_DEFINE
	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
#endif

	scanf("%d",&n);
	fi(0, n-1){
		int x, y;
		scanf("%d %d",&x,&y);
		--x;--y;
		e[x].pb(y);
		e[y].pb(x);
	}	
	f[0] = 1;
	fi(1, N) f[i] = mul(f[i-1], i);
	fi(0, 2) invn[i] = invf[i] = 1;
	fi(2, N){
		invn[i] = mul(MOD - MOD/i, invn[MOD%i]);
		invf[i] = mul(invf[i-1], invn[i]);
//		if(i < 10)	cerr << i << " " << invn[i] << endl;
	}
	dfs(0);
	if(sz(c) == 2){
		printf("%d\n",mul(f[n/2],f[n/2]));
		return 0;
	}
//	for(int x : c) printf("c = %d\n",x);
	int s = 0;
	vi a;
	for(int y : e[c[0]]){
		if(q[y] > q[c[0]]) continue;
		s += q[y];
		a.pb(q[y]);
	}
	if(n-1-s > 0) a.pb(n-1-s);
	d[0][0] = 1;
	fi(0, sz(a)) fj(0, n) fo(0, a[i]+1){
		if(j + o >= N) continue;
		int v0 = d[i][j];
		int v1 = getc(a[i], o);
	//	cerr << "v1 = " << v1 << endl;
		v1 = mul(v1, v1);
		v1 = mul(v1, f[o]);
		v1 = mul(v1, v0);
		add(d[i+1][j+o], v1);
	}			    	
//	fi(0, n+1) cerr << "d[i] = " << i << " " << d[sz(a)][i] << endl;
//	for(int x : a) cerr << x << endl;
	int ans = 0;
	fi(0, n){		
		int v0 = d[sz(a)][i];
	//	cerr << v0 << endl;
		int v1 = f[n-i];
		int v = mul(v0, v1);
		if(i&1) v = -v;
		add(ans, v);
	}
//	ans = mul(ans, n);
	printf("%d\n",ans);
	
#ifdef LOCAL_DEFINE
	fprintf(stderr, "ELAPSED TIME: %.3lf\n", (ld) clock() / CLOCKS_PER_SEC);
#endif	
	
	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<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<deque>
#include<functional>
#include<ctime>
#include<cassert>
#include<cstring>
using namespace std;

#define sz(x) (int)(x.size())
#define fi(a,b) for(int i=a;i<b;++i)
#define fj(a,b) for(int j=a;j<b;++j)
#define fo(a,b) for(int o=a;o<b;++o)
#define fdi(a,b) for(int i=a-1;i>=b;--i)
#define fdj(a,b) for(int j=a-1;j>=b;--j)
#define fdo(a,b) for(int o=a-1;o>=b;--o)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef double ld;
typedef vector<int> vi;

template<class T> bool uin(T &a, T b){ return (a > b ? a = b, true : false); }
template<class T> bool uax(T &a, T b){ return (a < b ? a = b, true : false); }

/////////////////////////////////

int const MOD = 1e9 + 7;
int const N = 5e3 + 41;

int f[N], invf[N], invn[N];
int n;
vi e[N];
int d[N][N];

void add(int &a, int b){
	a += b;
	while(a >= MOD) a -= MOD;
	while(a < 0) a += MOD;
}

int mul(int a, int b){
	return (ll) a * b % MOD;
}

int q[N];
vi c;

void dfs(int x, int p = -1){
	int mq = 0;
	q[x] = 1;
	for(int y : e[x]){
		if(y == p) continue;
		dfs(y, x);
		q[x] += q[y];
		uax(mq, q[y]);
	}
	uax(mq, n-q[x]);
	if(mq * 2 <= n) c.pb(x);
}

int getc(int n, int k){
	int res = f[n];
	res = mul(res, invf[k]);
	res = mul(res, invf[n-k]);
	return res;
}

int main(){
#ifdef LOCAL_DEFINE
	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
#endif

	scanf("%d",&n);
	fi(0, n-1){
		int x, y;
		scanf("%d %d",&x,&y);
		--x;--y;
		e[x].pb(y);
		e[y].pb(x);
	}	
	f[0] = 1;
	fi(1, N) f[i] = mul(f[i-1], i);
	fi(0, 2) invn[i] = invf[i] = 1;
	fi(2, N){
		invn[i] = mul(MOD - MOD/i, invn[MOD%i]);
		invf[i] = mul(invf[i-1], invn[i]);
//		if(i < 10)	cerr << i << " " << invn[i] << endl;
	}
	dfs(0);
	if(sz(c) == 2){
		printf("%d\n",mul(f[n/2],f[n/2]));
		return 0;
	}
//	for(int x : c) printf("c = %d\n",x);
	int s = 0;
	vi a;
	for(int y : e[c[0]]){
		if(q[y] > q[c[0]]) continue;
		s += q[y];
		a.pb(q[y]);
	}
	if(n-1-s > 0) a.pb(n-1-s);
	d[0][0] = 1;
	fi(0, sz(a)) fj(0, n) fo(0, a[i]+1){
		if(j + o >= N) continue;
		int v0 = d[i][j];
		int v1 = getc(a[i], o);
	//	cerr << "v1 = " << v1 << endl;
		v1 = mul(v1, v1);
		v1 = mul(v1, f[o]);
		v1 = mul(v1, v0);
		add(d[i+1][j+o], v1);
	}			    	
//	fi(0, n+1) cerr << "d[i] = " << i << " " << d[sz(a)][i] << endl;
//	for(int x : a) cerr << x << endl;
	int ans = 0;
	fi(0, n){		
		int v0 = d[sz(a)][i];
	//	cerr << v0 << endl;
		int v1 = f[n-i];
		int v = mul(v0, v1);
		if(i&1) v = -v;
		add(ans, v);
	}
//	ans = mul(ans, n);
	printf("%d\n",ans);
	
#ifdef LOCAL_DEFINE
	fprintf(stderr, "ELAPSED TIME: %.3lf\n", (ld) clock() / CLOCKS_PER_SEC);
#endif	
	
	return 0;
}

```