#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;

#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ldb ldouble

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 19;
int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<n;i++)
#define Se second
#define Fi first

const int MX = 5005;
const int MM = 1000000007;

int N, a, b;
vector<int> T[MX];
int cnt[MX];

int get_cnt(int x, int p = -1){
	cnt[x] = 1;
	for(int c : T[x]){
		if( c == p ) continue;
		cnt[x] += get_cnt(c, x);
	}
	return cnt[x];
}

ll F[MX], I[MX], FI[MX];

ll sq(ll x){ return x*x % MM; }

int main()
{
	F[0] = FI[0] = 1; I[1] = 1;
	for(int i = 2; i < MX; i++) I[i] = (MM - I[MM%i]) * (MM/i) % MM;
	for(int i = 1; i < MX; i++) F[i] = F[i-1] * i % MM;
	for(int i = 1; i < MX; i++) FI[i] = FI[i-1] * I[i] % MM;
	scanf("%d", &N);
	for(int i = 1; i < N; i++){
		scanf("%d%d", &a, &b);
		T[a].push_back(b);
		T[b].push_back(a);
	}
	int r = 1;
	get_cnt(r);
	while(1){
		int mx = T[r][0];
		for(int c : T[r]){
			if( cnt[mx] < cnt[c] )mx = c;
		}
		if( cnt[mx]*2 <= cnt[r] ) break;
		cnt[r] -= cnt[mx];
		cnt[mx] += cnt[r];
		r = mx;
	}

	vector<int> L;
	ll arr[2][MX] = {}, *S = arr[0], *E = arr[1];
	for(int c : T[r]) L.push_back(cnt[c]);
	S[0] = 1;
	for(int c : L){
		for(int i = 0; i < MX; i++) E[i] = 0;
		for(int i = 0; i <= c; i++){
			for(int j = i; j <= N; j++){
				E[j] = (E[j] + S[j-i] * F[c] % MM * FI[c-i] % MM * F[c] % MM * FI[i] % MM * FI[c-i]) % MM;
			}
		}
		swap(S, E);
	}

	ll ans = 0;
	for(int i = 0; i <= N-1; i++){
		if( i&1 ) ans = (ans + MM - S[i] * F[N-i] % MM);
		else ans = (ans + S[i] * F[N-i]) % MM;
	}
	printf("%lld\n", ans % MM);
}

### Prompt

Your task is to create a CPP solution 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 <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;

#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ldb ldouble

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 19;
int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<n;i++)
#define Se second
#define Fi first

const int MX = 5005;
const int MM = 1000000007;

int N, a, b;
vector<int> T[MX];
int cnt[MX];

int get_cnt(int x, int p = -1){
	cnt[x] = 1;
	for(int c : T[x]){
		if( c == p ) continue;
		cnt[x] += get_cnt(c, x);
	}
	return cnt[x];
}

ll F[MX], I[MX], FI[MX];

ll sq(ll x){ return x*x % MM; }

int main()
{
	F[0] = FI[0] = 1; I[1] = 1;
	for(int i = 2; i < MX; i++) I[i] = (MM - I[MM%i]) * (MM/i) % MM;
	for(int i = 1; i < MX; i++) F[i] = F[i-1] * i % MM;
	for(int i = 1; i < MX; i++) FI[i] = FI[i-1] * I[i] % MM;
	scanf("%d", &N);
	for(int i = 1; i < N; i++){
		scanf("%d%d", &a, &b);
		T[a].push_back(b);
		T[b].push_back(a);
	}
	int r = 1;
	get_cnt(r);
	while(1){
		int mx = T[r][0];
		for(int c : T[r]){
			if( cnt[mx] < cnt[c] )mx = c;
		}
		if( cnt[mx]*2 <= cnt[r] ) break;
		cnt[r] -= cnt[mx];
		cnt[mx] += cnt[r];
		r = mx;
	}

	vector<int> L;
	ll arr[2][MX] = {}, *S = arr[0], *E = arr[1];
	for(int c : T[r]) L.push_back(cnt[c]);
	S[0] = 1;
	for(int c : L){
		for(int i = 0; i < MX; i++) E[i] = 0;
		for(int i = 0; i <= c; i++){
			for(int j = i; j <= N; j++){
				E[j] = (E[j] + S[j-i] * F[c] % MM * FI[c-i] % MM * F[c] % MM * FI[i] % MM * FI[c-i]) % MM;
			}
		}
		swap(S, E);
	}

	ll ans = 0;
	for(int i = 0; i <= N-1; i++){
		if( i&1 ) ans = (ans + MM - S[i] * F[N-i] % MM);
		else ans = (ans + S[i] * F[N-i]) % MM;
	}
	printf("%lld\n", ans % MM);
}

```