#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MOD=1e9+7;
inline int add(int a,int b)
{a+=b;return a>=MOD?a-MOD:a;}
inline void Add(int &a,int b)
{a+=b;a>=MOD?a-=MOD:1;}
inline int mul(int a,int b)
{return 1LL*a*b%MOD;}
inline void Mul(int &a,int b)
{a=1LL*a*b%MOD;}
int ksm(int a,int b)
{
	int ans=1;
	for(;b;b>>=1,Mul(a,a))
		if(b&1)Mul(ans,a);
	return ans;
}
const int Q=5555;
vector<int> g[Q];
int rt,ct=0,n;
int si[Q];
void dfs(int x,int last)
{
	int mx=0;
	si[x]=1;
	for(int y :g[x]){
		if(y==last)continue;
		dfs(y,x);
		si[x]+=si[y];
		mx=max(mx,si[y]);
	}
	mx=max(mx,n-si[x]);
	if((mx<<1)<=n)++ct,rt=x;
}
int f[Q];
int fac[Q],ifac[Q];
inline int C(int n,int m)
{return mul(fac[n],mul(ifac[m],ifac[n-m]));}
inline int P2(int x)
{return mul(x,x);}
int main()
{
	scanf("%d",&n);
	fac[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=mul(fac[i-1],i);
	ifac[n]=ksm(fac[n],MOD-2);
	for(int i=n;i;--i)
		ifac[i-1]=mul(ifac[i],i);
	for(int i=1,x,y;i<n;i++)
		scanf("%d%d",&x,&y),g[x].push_back(y),g[y].push_back(x);
	dfs(1,0);
	if(ct>1)return 0&printf("%d\n",mul(fac[n/2],fac[n/2]));
	dfs(rt,0);
	int maxn=0;
	f[0]=1;
	for(int y:g[rt]){
		int val=si[y];
		maxn+=val; 
		for(int j=maxn;j;--j)
			for(int k=min(j,val);k;--k)
				Add(f[j],mul(f[j-k],mul(P2(C(val,k)),fac[k])));
	}
	int als=0;
	for(int i=0,ty=1;i<=n;i++,ty=MOD-ty)
		Add(als,mul(ty,mul(f[i],fac[n-i])));
	printf("%d\n",als);
	return 0;
}
### Prompt

Develop a solution in CPP 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 <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MOD=1e9+7;
inline int add(int a,int b)
{a+=b;return a>=MOD?a-MOD:a;}
inline void Add(int &a,int b)
{a+=b;a>=MOD?a-=MOD:1;}
inline int mul(int a,int b)
{return 1LL*a*b%MOD;}
inline void Mul(int &a,int b)
{a=1LL*a*b%MOD;}
int ksm(int a,int b)
{
	int ans=1;
	for(;b;b>>=1,Mul(a,a))
		if(b&1)Mul(ans,a);
	return ans;
}
const int Q=5555;
vector<int> g[Q];
int rt,ct=0,n;
int si[Q];
void dfs(int x,int last)
{
	int mx=0;
	si[x]=1;
	for(int y :g[x]){
		if(y==last)continue;
		dfs(y,x);
		si[x]+=si[y];
		mx=max(mx,si[y]);
	}
	mx=max(mx,n-si[x]);
	if((mx<<1)<=n)++ct,rt=x;
}
int f[Q];
int fac[Q],ifac[Q];
inline int C(int n,int m)
{return mul(fac[n],mul(ifac[m],ifac[n-m]));}
inline int P2(int x)
{return mul(x,x);}
int main()
{
	scanf("%d",&n);
	fac[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=mul(fac[i-1],i);
	ifac[n]=ksm(fac[n],MOD-2);
	for(int i=n;i;--i)
		ifac[i-1]=mul(ifac[i],i);
	for(int i=1,x,y;i<n;i++)
		scanf("%d%d",&x,&y),g[x].push_back(y),g[y].push_back(x);
	dfs(1,0);
	if(ct>1)return 0&printf("%d\n",mul(fac[n/2],fac[n/2]));
	dfs(rt,0);
	int maxn=0;
	f[0]=1;
	for(int y:g[rt]){
		int val=si[y];
		maxn+=val; 
		for(int j=maxn;j;--j)
			for(int k=min(j,val);k;--k)
				Add(f[j],mul(f[j-k],mul(P2(C(val,k)),fac[k])));
	}
	int als=0;
	for(int i=0,ty=1;i<=n;i++,ty=MOD-ty)
		Add(als,mul(ty,mul(f[i],fac[n-i])));
	printf("%d\n",als);
	return 0;
}
```