#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pdi pair<db,int>
#define mp make_pair
#define pb push_back
#define enter putchar('\n')
#define space putchar(' ')
#define eps 1e-8
#define mo 974711
#define MAXN 5005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 + c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
const int MOD = 1000000007;
int N;
struct node {
    int to,next;
}E[MAXN * 2];
int head[MAXN],sumE,siz[MAXN],son[MAXN];
int C[MAXN][MAXN],fac[MAXN],val[MAXN],tot,f[MAXN];
int inc(int a,int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
    return 1LL * a * b % MOD;
}
void add(int u,int v) {
    E[++sumE].next = head[u];
    E[sumE].to = v;
    head[u] = sumE;
}
void dfs(int u,int fa) {
    siz[u] = 1;
    for(int i = head[u] ; i ; i = E[i].next) {
	int v = E[i].to;
	if(v != fa) {
	    dfs(v,u);
	    siz[u] += siz[v];
	    son[u] = max(son[u],siz[v]);
	}
    }
    son[u] = max(son[u],N - siz[u]);
}
void Init() {
    read(N);
    int x,y;
    for(int i = 1 ; i < N ; ++i) {
	read(x);read(y);
	add(x,y);add(y,x);
    }
    C[0][0] = 1;
    for(int i = 1 ; i <= N ; ++i) {
	C[i][0] = 1;
	for(int j = 1 ; j <= N ; ++j) {
	    C[i][j] = inc(C[i - 1][j],C[i - 1][j - 1]);
	}
    }
    fac[0] = 1;
    for(int i = 1 ; i <= N ; ++i) fac[i] = mul(fac[i - 1],i);
}
void Solve() {
    dfs(1,0);
    int g = 1;
    for(int i = 2 ; i <= N ; ++i) {
	if(son[i] < son[g]) g = i;
    }
    if(N % 2 == 0 && son[g] == N / 2) {
	out(mul(fac[N / 2],fac[N / 2]));enter;return;
    }
    for(int i = head[g] ; i ; i = E[i].next) {
	int v = E[i].to;
	if(siz[v] < siz[g]) val[++tot] = siz[v];
    }
    if(g != 1) val[++tot] = N - siz[g];
    int s = 0;f[0] = 1;
    for(int i = 1 ; i <= tot ; ++i) {
	for(int t = s + val[i] ; t >= 0 ; --t) {
	    for(int j = 1 ; j <= val[i] ; ++j) {
		if(j > t) break;
		f[t] = inc(f[t],mul(mul(f[t - j],C[val[i]][j]),mul(C[val[i]][j],fac[j])));
	    }
	}
	s += val[i];
    }
    int t = 1,ans = 0;
    for(int i = 0 ; i <= N - 1; ++i) {
	ans = inc(ans,mul(mul(t,f[i]),fac[N - i]));
	t = mul(t,MOD - 1);
    }
    out(ans);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Init();
    Solve();
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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>
#define fi first
#define se second
#define pii pair<int,int>
#define pdi pair<db,int>
#define mp make_pair
#define pb push_back
#define enter putchar('\n')
#define space putchar(' ')
#define eps 1e-8
#define mo 974711
#define MAXN 5005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 + c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
const int MOD = 1000000007;
int N;
struct node {
    int to,next;
}E[MAXN * 2];
int head[MAXN],sumE,siz[MAXN],son[MAXN];
int C[MAXN][MAXN],fac[MAXN],val[MAXN],tot,f[MAXN];
int inc(int a,int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
    return 1LL * a * b % MOD;
}
void add(int u,int v) {
    E[++sumE].next = head[u];
    E[sumE].to = v;
    head[u] = sumE;
}
void dfs(int u,int fa) {
    siz[u] = 1;
    for(int i = head[u] ; i ; i = E[i].next) {
	int v = E[i].to;
	if(v != fa) {
	    dfs(v,u);
	    siz[u] += siz[v];
	    son[u] = max(son[u],siz[v]);
	}
    }
    son[u] = max(son[u],N - siz[u]);
}
void Init() {
    read(N);
    int x,y;
    for(int i = 1 ; i < N ; ++i) {
	read(x);read(y);
	add(x,y);add(y,x);
    }
    C[0][0] = 1;
    for(int i = 1 ; i <= N ; ++i) {
	C[i][0] = 1;
	for(int j = 1 ; j <= N ; ++j) {
	    C[i][j] = inc(C[i - 1][j],C[i - 1][j - 1]);
	}
    }
    fac[0] = 1;
    for(int i = 1 ; i <= N ; ++i) fac[i] = mul(fac[i - 1],i);
}
void Solve() {
    dfs(1,0);
    int g = 1;
    for(int i = 2 ; i <= N ; ++i) {
	if(son[i] < son[g]) g = i;
    }
    if(N % 2 == 0 && son[g] == N / 2) {
	out(mul(fac[N / 2],fac[N / 2]));enter;return;
    }
    for(int i = head[g] ; i ; i = E[i].next) {
	int v = E[i].to;
	if(siz[v] < siz[g]) val[++tot] = siz[v];
    }
    if(g != 1) val[++tot] = N - siz[g];
    int s = 0;f[0] = 1;
    for(int i = 1 ; i <= tot ; ++i) {
	for(int t = s + val[i] ; t >= 0 ; --t) {
	    for(int j = 1 ; j <= val[i] ; ++j) {
		if(j > t) break;
		f[t] = inc(f[t],mul(mul(f[t - j],C[val[i]][j]),mul(C[val[i]][j],fac[j])));
	    }
	}
	s += val[i];
    }
    int t = 1,ans = 0;
    for(int i = 0 ; i <= N - 1; ++i) {
	ans = inc(ans,mul(mul(t,f[i]),fac[N - i]));
	t = mul(t,MOD - 1);
    }
    out(ans);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Init();
    Solve();
}

```