#include <bits/stdc++.h>

using namespace std;

#define ll 			long long
#define db			double
#define up(i,j,n)		for (int i = j; i <= n; i++)
#define down(i,j,n)	for (int i = j; i >= n; i--)
#define cadd(a,b)		a = add (a, b)
#define cpop(a,b)		a = pop (a, b)
#define cmul(a,b)		a = mul (a, b)
#define pr			pair<int, int>
#define fi			first
#define se			second
#define SZ(x)		(int)x.size()
#define bin(i)		(1 << (i))
#define Auto(i,node)	for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}

const int MAXN = 5005;;
const int oo = 0x3f3f3f3f;
const int mod = 1e9 + 7;

inline int add(int a, int b){a += b; return a >= mod ? a - mod : a;}
inline int pop(int a, int b){a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b){return 1LL * a * b % mod;}

int N, fac[MAXN], f[MAXN], g[MAXN], a[MAXN], C[MAXN][MAXN], M = 0, ans = 0;

struct edge {
	int y, next;
}e[MAXN << 1];
int LINK[MAXN], len = 0, siz[MAXN], mxsiz[MAXN], rt[MAXN], rts;
inline void ins(int x, int y){
	e[++len].next = LINK[x]; LINK[x] = len;
	e[len].y = y; 
}
inline void Ins(int x, int y){
	ins(x, y);
	ins(y, x);
}

void DFS(int node, int fa){
	siz[node] = 1; mxsiz[node] = 0;
	Auto (i, node) if (e[i].y != fa) {
		DFS(e[i].y, node);
		siz[node] += siz[e[i].y];
		cmax(mxsiz[node], siz[e[i].y]);
	}
	cmax(mxsiz[node], N - siz[node]);
	if (mxsiz[node] < mxsiz[rt[rts]]) rt[rts = 1] = node;
	else if (mxsiz[node] == mxsiz[rt[rts]]) rt[++rts] = node;
}

void Fix(int node, int fa){
	siz[node] = 1;
	Auto (i, node) if (e[i].y != fa) {
		Fix(e[i].y, node);
		siz[node] += siz[e[i].y];
	}
}

int main(){
	scanf("%d", &N);
	C[0][0] = 1;
	up (i, 1, N) {
		C[i][0] = 1;
		up (j, 1, i) C[i][j] = add(C[i - 1][j - 1], C[i - 1][j]);
	} 
	fac[0] = 1;
	up (i, 1, N) fac[i] = mul(i, fac[i - 1]);
	up (i, 2, N) {
		int x, y;
		scanf("%d%d", &x, &y);
		Ins(x, y);
	}
	mxsiz[0] = oo;
	DFS(1, 0);
	if (rts == 2) {
		Fix(rt[1], rt[2]);
		Fix(rt[2], rt[1]);
		printf("%d\n", mul(fac[siz[rt[1]]], fac[siz[rt[2]]]));
		return 0;
	}
	Fix(rt[1], 0); 
	Auto (i, rt[1]) a[++M] = siz[e[i].y];
	f[0] = 1;
	int cur = 0;
	up (i, 1, M) {
		memset(g, 0, sizeof(int) * (cur + 1));
		up (j, 0, cur) up (k, 0, a[i]) cadd(g[j + k], mul(f[j], mul(C[a[i]][k], mul(C[a[i]][k], fac[k]))));
		cur += a[i];
		memcpy(f, g, sizeof(int) * (cur + 1));
	} 
	up (i, 0, N) {
		if (i & 1) 	cpop(ans, mul(f[i], fac[N - i]));
		else		cadd(ans, mul(f[i], fac[N - i]));
	} 
	printf("%d\n", ans);
	return 0;
}

### 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>

using namespace std;

#define ll 			long long
#define db			double
#define up(i,j,n)		for (int i = j; i <= n; i++)
#define down(i,j,n)	for (int i = j; i >= n; i--)
#define cadd(a,b)		a = add (a, b)
#define cpop(a,b)		a = pop (a, b)
#define cmul(a,b)		a = mul (a, b)
#define pr			pair<int, int>
#define fi			first
#define se			second
#define SZ(x)		(int)x.size()
#define bin(i)		(1 << (i))
#define Auto(i,node)	for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}

const int MAXN = 5005;;
const int oo = 0x3f3f3f3f;
const int mod = 1e9 + 7;

inline int add(int a, int b){a += b; return a >= mod ? a - mod : a;}
inline int pop(int a, int b){a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b){return 1LL * a * b % mod;}

int N, fac[MAXN], f[MAXN], g[MAXN], a[MAXN], C[MAXN][MAXN], M = 0, ans = 0;

struct edge {
	int y, next;
}e[MAXN << 1];
int LINK[MAXN], len = 0, siz[MAXN], mxsiz[MAXN], rt[MAXN], rts;
inline void ins(int x, int y){
	e[++len].next = LINK[x]; LINK[x] = len;
	e[len].y = y; 
}
inline void Ins(int x, int y){
	ins(x, y);
	ins(y, x);
}

void DFS(int node, int fa){
	siz[node] = 1; mxsiz[node] = 0;
	Auto (i, node) if (e[i].y != fa) {
		DFS(e[i].y, node);
		siz[node] += siz[e[i].y];
		cmax(mxsiz[node], siz[e[i].y]);
	}
	cmax(mxsiz[node], N - siz[node]);
	if (mxsiz[node] < mxsiz[rt[rts]]) rt[rts = 1] = node;
	else if (mxsiz[node] == mxsiz[rt[rts]]) rt[++rts] = node;
}

void Fix(int node, int fa){
	siz[node] = 1;
	Auto (i, node) if (e[i].y != fa) {
		Fix(e[i].y, node);
		siz[node] += siz[e[i].y];
	}
}

int main(){
	scanf("%d", &N);
	C[0][0] = 1;
	up (i, 1, N) {
		C[i][0] = 1;
		up (j, 1, i) C[i][j] = add(C[i - 1][j - 1], C[i - 1][j]);
	} 
	fac[0] = 1;
	up (i, 1, N) fac[i] = mul(i, fac[i - 1]);
	up (i, 2, N) {
		int x, y;
		scanf("%d%d", &x, &y);
		Ins(x, y);
	}
	mxsiz[0] = oo;
	DFS(1, 0);
	if (rts == 2) {
		Fix(rt[1], rt[2]);
		Fix(rt[2], rt[1]);
		printf("%d\n", mul(fac[siz[rt[1]]], fac[siz[rt[2]]]));
		return 0;
	}
	Fix(rt[1], 0); 
	Auto (i, rt[1]) a[++M] = siz[e[i].y];
	f[0] = 1;
	int cur = 0;
	up (i, 1, M) {
		memset(g, 0, sizeof(int) * (cur + 1));
		up (j, 0, cur) up (k, 0, a[i]) cadd(g[j + k], mul(f[j], mul(C[a[i]][k], mul(C[a[i]][k], fac[k]))));
		cur += a[i];
		memcpy(f, g, sizeof(int) * (cur + 1));
	} 
	up (i, 0, N) {
		if (i & 1) 	cpop(ans, mul(f[i], fac[N - i]));
		else		cadd(ans, mul(f[i], fac[N - i]));
	} 
	printf("%d\n", ans);
	return 0;
}

```