#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

int n;
vector <int> E[5050];
int down[5050];
const int MOD = 1e9 + 7;

void pdfs(int x, int fa) {
	down[x] = 1;
	for(int e : E[x]) if(e != fa) {
		pdfs(e, x);
		down[x] += down[e];
	}
}

int C[5050][5050], F[5050];
int D[5050][5050], temp2[5050];

int Get(vector <int> L) {
	int n = szz(L);
	for(int i=1;i<=n;i++) {
		int ai = L[i-1];
		D[i][0] = 1;
		for(int j=1;j<=ai;j++) D[i][j] = (ll) D[i][j-1] * (ai - j + 1) % MOD;
		for(int j=0;j<=ai;j++) D[i][j] = D[i][j] * (ll) C[ai][j] % MOD;
	}
	int s = L[0];
	for(int i=2;i<=n;i++) {
		int ai = L[i-1];
		for(int j=0;j<=s+ai;j++) temp2[j] = 0;
		for(int j=0;j<=s;j++) {
			for(int k=0;k<=ai;k++) {
				temp2[j+k] = (temp2[j+k] + (ll) D[i-1][j] * D[i][k]) % MOD;
			}
		}
		for(int j=0;j<=s+ai;j++) D[i][j] = temp2[j];
		s += ai;
	}
	int ans = 0;
	for(int i=0;i<=s;i++) {
		ll v = F[s-i] * (ll)D[n][i] % MOD;
		if(i & 1) ans = (ans - v + MOD) % MOD;
		else ans = (ans + v) % MOD;
	}
	return ans;
}

void solve() {
	F[0] = 1;
	for(int i=0;i<5050;i++) {
		C[i][0] = 1;
		if(i) F[i] = (ll) i * F[i-1] % MOD;
		for(int j=1;j<=i;j++) {
			C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
		}
	}
	scanf("%d", &n);
	rep(i, n-1) {
		int x, y; scanf("%d%d", &x, &y);
		E[x].pb(y);
		E[y].pb(x);
	}
	pdfs(1, -1);
	int h = n / 2, c = 1;
	while(1) {
		int f = 0;
		for(int e : E[c]) if(down[e] < down[c] && down[e] > h) {
			c = e; f = 1; break;
		}
		if(f == 0) break;
	}
	pdfs(c, -1);
	vector <int> A;
	for(int e : E[c]) A.pb(down[e]);
	ll ans = Get(A); A.pb(1);
	ans = (ans + Get(A)) % MOD;
	printf("%lld\n", ans);
}

int main(){
	int Tc = 1; // scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		solve();
	}
	return 0;
}



### Prompt

In Cpp, your task is to solve 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 <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

int n;
vector <int> E[5050];
int down[5050];
const int MOD = 1e9 + 7;

void pdfs(int x, int fa) {
	down[x] = 1;
	for(int e : E[x]) if(e != fa) {
		pdfs(e, x);
		down[x] += down[e];
	}
}

int C[5050][5050], F[5050];
int D[5050][5050], temp2[5050];

int Get(vector <int> L) {
	int n = szz(L);
	for(int i=1;i<=n;i++) {
		int ai = L[i-1];
		D[i][0] = 1;
		for(int j=1;j<=ai;j++) D[i][j] = (ll) D[i][j-1] * (ai - j + 1) % MOD;
		for(int j=0;j<=ai;j++) D[i][j] = D[i][j] * (ll) C[ai][j] % MOD;
	}
	int s = L[0];
	for(int i=2;i<=n;i++) {
		int ai = L[i-1];
		for(int j=0;j<=s+ai;j++) temp2[j] = 0;
		for(int j=0;j<=s;j++) {
			for(int k=0;k<=ai;k++) {
				temp2[j+k] = (temp2[j+k] + (ll) D[i-1][j] * D[i][k]) % MOD;
			}
		}
		for(int j=0;j<=s+ai;j++) D[i][j] = temp2[j];
		s += ai;
	}
	int ans = 0;
	for(int i=0;i<=s;i++) {
		ll v = F[s-i] * (ll)D[n][i] % MOD;
		if(i & 1) ans = (ans - v + MOD) % MOD;
		else ans = (ans + v) % MOD;
	}
	return ans;
}

void solve() {
	F[0] = 1;
	for(int i=0;i<5050;i++) {
		C[i][0] = 1;
		if(i) F[i] = (ll) i * F[i-1] % MOD;
		for(int j=1;j<=i;j++) {
			C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
		}
	}
	scanf("%d", &n);
	rep(i, n-1) {
		int x, y; scanf("%d%d", &x, &y);
		E[x].pb(y);
		E[y].pb(x);
	}
	pdfs(1, -1);
	int h = n / 2, c = 1;
	while(1) {
		int f = 0;
		for(int e : E[c]) if(down[e] < down[c] && down[e] > h) {
			c = e; f = 1; break;
		}
		if(f == 0) break;
	}
	pdfs(c, -1);
	vector <int> A;
	for(int e : E[c]) A.pb(down[e]);
	ll ans = Get(A); A.pb(1);
	ans = (ans + Get(A)) % MOD;
	printf("%lld\n", ans);
}

int main(){
	int Tc = 1; // scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		solve();
	}
	return 0;
}



```