#include<bits/stdc++.h>
#define ll long long
#define N 5010
#define mod 1000000007
#define rep(i,l,r) for (int i=l;i<=r;++i)
using namespace std;
ll jc[N],inv[N],f[N],g[N],res;
int n,x,y,sz[N],a[N],tot,cnt;
vector<int>G[N];
ll K(ll x,int y=mod-2){
	ll t=1; for (;y;y>>=1,x=x*x%mod) if (y&1) t=t*x%mod; return t;
}
ll C(int x,int y){
	return jc[x]* inv[y]%mod *inv[x-y]%mod;
}
void U(ll &x,ll y){
	if ((x+=y)>=mod) x%=mod;
}

void dfs(int x,int fa){
	int mx=0; sz[x]=1;
	for (auto y:G[x]) if (y-fa)
		dfs(y,x), sz[x]+=sz[y], mx=max(mx,sz[y]);
	mx=max(mx,n-sz[x]);
	if (mx*2==n) exit(!(cout<<jc[mx]*jc[mx]%mod));
	if (mx*2>n) return;
	for (auto y:G[x]) if (y-fa) a[++cnt]=sz[y];
	if (x-1) a[++cnt]=n-sz[x];
	memset(f,0,sizeof f); f[tot=0]=1;
	rep(i,1,cnt){
		memset(g,0,sizeof g);
		rep(j,0,a[i]) rep(k,0,tot)
			U(g[k+j],f[k]*C(a[i],j)%mod*C(a[i],j)%mod*jc[j]%mod);
		memcpy(f,g,sizeof g);
		tot+=a[i];
	}
	rep(i,0,tot) U(res,mod+(i&1?-1:1)*f[i]*jc[n-i]%mod);
	exit(!(cout<<res));
}

int main(){
	jc[0]=1; rep(i,1,N-1) jc[i]=jc[i-1]*i%mod;
	inv[N-1]=K(jc[N-1]); for(int i=N;i--;) inv[i-1]=inv[i]*i%mod;
	cin>>n;
	rep(i,1,n-1) cin>>x>>y, G[x].push_back(y), G[y].push_back(x);
	dfs(1,0);
}
### 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<bits/stdc++.h>
#define ll long long
#define N 5010
#define mod 1000000007
#define rep(i,l,r) for (int i=l;i<=r;++i)
using namespace std;
ll jc[N],inv[N],f[N],g[N],res;
int n,x,y,sz[N],a[N],tot,cnt;
vector<int>G[N];
ll K(ll x,int y=mod-2){
	ll t=1; for (;y;y>>=1,x=x*x%mod) if (y&1) t=t*x%mod; return t;
}
ll C(int x,int y){
	return jc[x]* inv[y]%mod *inv[x-y]%mod;
}
void U(ll &x,ll y){
	if ((x+=y)>=mod) x%=mod;
}

void dfs(int x,int fa){
	int mx=0; sz[x]=1;
	for (auto y:G[x]) if (y-fa)
		dfs(y,x), sz[x]+=sz[y], mx=max(mx,sz[y]);
	mx=max(mx,n-sz[x]);
	if (mx*2==n) exit(!(cout<<jc[mx]*jc[mx]%mod));
	if (mx*2>n) return;
	for (auto y:G[x]) if (y-fa) a[++cnt]=sz[y];
	if (x-1) a[++cnt]=n-sz[x];
	memset(f,0,sizeof f); f[tot=0]=1;
	rep(i,1,cnt){
		memset(g,0,sizeof g);
		rep(j,0,a[i]) rep(k,0,tot)
			U(g[k+j],f[k]*C(a[i],j)%mod*C(a[i],j)%mod*jc[j]%mod);
		memcpy(f,g,sizeof g);
		tot+=a[i];
	}
	rep(i,0,tot) U(res,mod+(i&1?-1:1)*f[i]*jc[n-i]%mod);
	exit(!(cout<<res));
}

int main(){
	jc[0]=1; rep(i,1,N-1) jc[i]=jc[i-1]*i%mod;
	inv[N-1]=K(jc[N-1]); for(int i=N;i--;) inv[i-1]=inv[i]*i%mod;
	cin>>n;
	rep(i,1,n-1) cin>>x>>y, G[x].push_back(y), G[y].push_back(x);
	dfs(1,0);
}
```