#include<stdio.h>
#include<bits/stdc++.h>
const int mod = 1e9+7;
int ad(int x,int y) { x+=y; return x>=mod?x-mod:x; }
int sb(int x,int y) { x-=y; return x<0?x+mod:x; }
int mu(int x,int y) { return 1ll*x*y%mod; }
void up(int &x,int y) { x+=y; if(x>=mod)x-=mod; }
using namespace std;
vector<int>ve[5005];
int f[5005][5005];
int RT;
int n;
int V[5005],TT,sz[5005];
void dfs(int x,int ba) {
	sz[x] = 1; 
	int sso = 0;
	for(auto y:ve[x]) {
		if(y==ba) continue;
		dfs(y,x);
		sso = max(sso,sz[y]);
		sz[x] += sz[y];
	}
	sso = max(sso,n-sz[x]);
	if(sso<=n/2) RT = (RT?-1:x);
}
int fac[5005],inv[5005];
int A(int x,int y) {
	return mu(fac[x],inv[x-y]);
}
int C(int x,int y) {
	return mu(fac[x],mu(inv[x-y],inv[y]));
}

int main() {
	scanf("%d",&n);
	for(int i=1;i<n;i++) {
		int x,y; scanf("%d%d",&x,&y);
		ve[x].push_back(y);
		ve[y].push_back(x);
	}
	fac[0] = 1;
	for(int i=1;i<=n;i++) fac[i] = mu(fac[i-1],i);
	inv[0] = inv[1] = 1;
	for(int i=2;i<=n;i++) inv[i] = mu(inv[mod%i],mod-mod/i);
	for(int i=2;i<=n;i++) inv[i] = mu(inv[i-1],inv[i]);
	dfs(1,0);
	if(RT==-1) {
		printf("%d",mu(fac[n/2],fac[n/2]));
		return 0;
	}
	if(RT!=1) V[++TT] = n-sz[RT];
	for(auto y:ve[RT]) {
		if(sz[y]<sz[RT]) V[++TT] = sz[y];
	}
	f[0][0] = 1;
	int tot = 0;
	for(int i=1;i<=TT;i++) {
		tot += V[i];
		for(int j=0;j<=tot;j++) {
			for(int k=0;k<=min(V[i],j);k++) {
				up(f[i][j],mu(f[i-1][j-k],mu( C(V[i],k),A(V[i],k) )));
			}
		}
	}
	int ans = 0;
	for(int i=0;i<n;i++) {
		if(i&1) ans = sb(ans,mu(f[TT][i],fac[n-i]));
		else ans = ad(ans,mu(f[TT][i],fac[n-i]));
	}
	printf("%d",ans);
}
### Prompt

Generate 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<bits/stdc++.h>
const int mod = 1e9+7;
int ad(int x,int y) { x+=y; return x>=mod?x-mod:x; }
int sb(int x,int y) { x-=y; return x<0?x+mod:x; }
int mu(int x,int y) { return 1ll*x*y%mod; }
void up(int &x,int y) { x+=y; if(x>=mod)x-=mod; }
using namespace std;
vector<int>ve[5005];
int f[5005][5005];
int RT;
int n;
int V[5005],TT,sz[5005];
void dfs(int x,int ba) {
	sz[x] = 1; 
	int sso = 0;
	for(auto y:ve[x]) {
		if(y==ba) continue;
		dfs(y,x);
		sso = max(sso,sz[y]);
		sz[x] += sz[y];
	}
	sso = max(sso,n-sz[x]);
	if(sso<=n/2) RT = (RT?-1:x);
}
int fac[5005],inv[5005];
int A(int x,int y) {
	return mu(fac[x],inv[x-y]);
}
int C(int x,int y) {
	return mu(fac[x],mu(inv[x-y],inv[y]));
}

int main() {
	scanf("%d",&n);
	for(int i=1;i<n;i++) {
		int x,y; scanf("%d%d",&x,&y);
		ve[x].push_back(y);
		ve[y].push_back(x);
	}
	fac[0] = 1;
	for(int i=1;i<=n;i++) fac[i] = mu(fac[i-1],i);
	inv[0] = inv[1] = 1;
	for(int i=2;i<=n;i++) inv[i] = mu(inv[mod%i],mod-mod/i);
	for(int i=2;i<=n;i++) inv[i] = mu(inv[i-1],inv[i]);
	dfs(1,0);
	if(RT==-1) {
		printf("%d",mu(fac[n/2],fac[n/2]));
		return 0;
	}
	if(RT!=1) V[++TT] = n-sz[RT];
	for(auto y:ve[RT]) {
		if(sz[y]<sz[RT]) V[++TT] = sz[y];
	}
	f[0][0] = 1;
	int tot = 0;
	for(int i=1;i<=TT;i++) {
		tot += V[i];
		for(int j=0;j<=tot;j++) {
			for(int k=0;k<=min(V[i],j);k++) {
				up(f[i][j],mu(f[i-1][j-k],mu( C(V[i],k),A(V[i],k) )));
			}
		}
	}
	int ans = 0;
	for(int i=0;i<n;i++) {
		if(i&1) ans = sb(ans,mu(f[TT][i],fac[n-i]));
		else ans = ad(ans,mu(f[TT][i],fac[n-i]));
	}
	printf("%d",ans);
}
```