#include<bits/stdc++.h>
#define For(i,l,r) for(int i = (l),i##end = (r);i <= i##end;i++)
#define Fordown(i,r,l) for(int i = (r),i##end = (l);i >= i##end;i--)
#define debug(x) cout << #x << " = " << x << endl

using namespace std;

typedef long long ll;

template <typename T> inline bool chkmin(T &x,T y) { return y < x ? x = y,1 : 0; }
template <typename T> inline bool chkmax(T &x,T y) { return x < y ? x = y,1 : 0; }

const int INF = 0x3f3f3f3f;
const int N = 5e3 + 10,mod = 1e9 + 7;

int to[N << 1],nex[N << 1],beg[N],fac[N],inv[N],sz[N],Maxsz[N],dp[2][N];
int e,rt,n;

inline int read() {
	int x = 0,flag = 1;
	char ch = getchar();
	while(!isdigit(ch) && ch != '-')ch = getchar();
	if(ch == '-')flag = -1,ch = getchar();
	while(isdigit(ch))x = (x << 3) + (x << 1) + (ch - '0'),ch = getchar();
	return x * flag;
}

inline void Add(int &x,int y) {
	if((x += y) >= mod) x -= mod;
}

inline void add(int x,int y) {
	to[++e] = y,nex[e] = beg[x],beg[x] = e;
}

inline int fpm(int a,int b) {
	int res = 1;
	while(b) {
		if(b & 1) res = 1ll * res * a % mod;
		a = 1ll * a * a % mod,b /= 2;
	}
	return res;
}

inline void init(int Lim) {
	fac[0] = 1;
	For(i,1,Lim) fac[i] = 1ll * fac[i - 1] * i % mod;
	inv[Lim] = fpm(fac[Lim],mod - 2);
	Fordown(i,Lim,1) inv[i - 1] = 1ll * inv[i] * i % mod;
}

inline void dfs_rt(int x,int fa) {
	sz[x] = 1,Maxsz[x] = 0;
	for(int i = beg[x];i;i = nex[i]) {
		if(to[i] == fa) continue;
		dfs_rt(to[i],x);
		sz[x] += sz[to[i]];
		chkmax(Maxsz[x],sz[to[i]]);
	}
	chkmax(Maxsz[x],n - sz[x]);
	if(Maxsz[x] < Maxsz[rt]) rt = x;
}

inline int C(int a,int b) {
	return 1ll * fac[a] * inv[b] % mod * inv[a - b] % mod;
}

inline int A(int a,int b) {
	return 1ll * fac[a] * inv[a - b] % mod;
}

int main() {

	n = read();
	init(n + 5);
	For(i,1,n - 1) {
		int x = read(),y = read();
		add(x,y),add(y,x);
	}

	Maxsz[0] = n + 1;
	dfs_rt(1,0),dfs_rt(rt,0);
	int cnt = 0;
	For(i,1,n) if(Maxsz[i] == Maxsz[rt]) cnt++;
	if(cnt == 2) return printf("%d\n",fpm(fac[n / 2],2)),0;

	int Sum = 0,Nex = 0,Cur = 1;
	dp[Cur][0] = 1;
	for(int i = beg[rt];i;i = nex[i]) {
		memset(dp[Nex],0,sizeof(dp[Nex]));
		For(j,0,Sum) For(k,0,sz[to[i]])
			Add(dp[Nex][j + k],1ll * dp[Cur][j] * C(sz[to[i]],k) % mod * A(sz[to[i]],k) % mod);
		Sum += sz[to[i]],swap(Cur,Nex);
	}
	int ans = 0;
	For(i,0,n)
		ans = (ans + (i & 1 ? -1ll : 1ll) * fac[n - i] * dp[Cur][i]) % mod;

	printf("%d\n",(ans + mod) % mod);

	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<bits/stdc++.h>
#define For(i,l,r) for(int i = (l),i##end = (r);i <= i##end;i++)
#define Fordown(i,r,l) for(int i = (r),i##end = (l);i >= i##end;i--)
#define debug(x) cout << #x << " = " << x << endl

using namespace std;

typedef long long ll;

template <typename T> inline bool chkmin(T &x,T y) { return y < x ? x = y,1 : 0; }
template <typename T> inline bool chkmax(T &x,T y) { return x < y ? x = y,1 : 0; }

const int INF = 0x3f3f3f3f;
const int N = 5e3 + 10,mod = 1e9 + 7;

int to[N << 1],nex[N << 1],beg[N],fac[N],inv[N],sz[N],Maxsz[N],dp[2][N];
int e,rt,n;

inline int read() {
	int x = 0,flag = 1;
	char ch = getchar();
	while(!isdigit(ch) && ch != '-')ch = getchar();
	if(ch == '-')flag = -1,ch = getchar();
	while(isdigit(ch))x = (x << 3) + (x << 1) + (ch - '0'),ch = getchar();
	return x * flag;
}

inline void Add(int &x,int y) {
	if((x += y) >= mod) x -= mod;
}

inline void add(int x,int y) {
	to[++e] = y,nex[e] = beg[x],beg[x] = e;
}

inline int fpm(int a,int b) {
	int res = 1;
	while(b) {
		if(b & 1) res = 1ll * res * a % mod;
		a = 1ll * a * a % mod,b /= 2;
	}
	return res;
}

inline void init(int Lim) {
	fac[0] = 1;
	For(i,1,Lim) fac[i] = 1ll * fac[i - 1] * i % mod;
	inv[Lim] = fpm(fac[Lim],mod - 2);
	Fordown(i,Lim,1) inv[i - 1] = 1ll * inv[i] * i % mod;
}

inline void dfs_rt(int x,int fa) {
	sz[x] = 1,Maxsz[x] = 0;
	for(int i = beg[x];i;i = nex[i]) {
		if(to[i] == fa) continue;
		dfs_rt(to[i],x);
		sz[x] += sz[to[i]];
		chkmax(Maxsz[x],sz[to[i]]);
	}
	chkmax(Maxsz[x],n - sz[x]);
	if(Maxsz[x] < Maxsz[rt]) rt = x;
}

inline int C(int a,int b) {
	return 1ll * fac[a] * inv[b] % mod * inv[a - b] % mod;
}

inline int A(int a,int b) {
	return 1ll * fac[a] * inv[a - b] % mod;
}

int main() {

	n = read();
	init(n + 5);
	For(i,1,n - 1) {
		int x = read(),y = read();
		add(x,y),add(y,x);
	}

	Maxsz[0] = n + 1;
	dfs_rt(1,0),dfs_rt(rt,0);
	int cnt = 0;
	For(i,1,n) if(Maxsz[i] == Maxsz[rt]) cnt++;
	if(cnt == 2) return printf("%d\n",fpm(fac[n / 2],2)),0;

	int Sum = 0,Nex = 0,Cur = 1;
	dp[Cur][0] = 1;
	for(int i = beg[rt];i;i = nex[i]) {
		memset(dp[Nex],0,sizeof(dp[Nex]));
		For(j,0,Sum) For(k,0,sz[to[i]])
			Add(dp[Nex][j + k],1ll * dp[Cur][j] * C(sz[to[i]],k) % mod * A(sz[to[i]],k) % mod);
		Sum += sz[to[i]],swap(Cur,Nex);
	}
	int ans = 0;
	For(i,0,n)
		ans = (ans + (i & 1 ? -1ll : 1ll) * fac[n - i] * dp[Cur][i]) % mod;

	printf("%d\n",(ans + mod) % mod);

	return 0;
}
```