#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#define ll long long
#define p 1000000007
using namespace std;
namespace ywy{
	typedef struct _b{
		int dest;int nxt;
	}bian;bian memchi[1000001];int gn=1,heads[5001];ll jc[5001],jcny[5001];ll dp[5001];
	inline void add(int s,int t){
		memchi[gn].dest=t;memchi[gn].nxt=heads[s];heads[s]=gn;gn++;
	}int size[5001],n;
	inline ll mi(int a,int b){
		ll ans=1,tmp=a;while(b){
			if(b&1)ans=(ans*tmp)%p;tmp=(tmp*tmp)%p;b>>=1;
		}return(ans);
	}vector<int> vec;
	void dfs(int pt,int baba){
		int mx=0;size[pt]=1;for(register int i=heads[pt];i;i=memchi[i].nxt){
			if(memchi[i].dest==baba)continue;dfs(memchi[i].dest,pt);size[pt]+=size[memchi[i].dest];
			mx=max(mx,size[memchi[i].dest]);
		}if(max(mx,n-size[pt])<=n/2)vec.push_back(pt);
	}
	void efs(int pt,int baba){
		size[pt]=1;for(register int i=heads[pt];i;i=memchi[i].nxt){
			if(memchi[i].dest==baba)continue;efs(memchi[i].dest,pt);size[pt]+=size[memchi[i].dest];
		}
	}
	inline ll cnm(int n,int m){
		if(n<m)return(0);ll cjr=jc[n];cjr*=jcny[m];cjr%=p;cjr*=jcny[n-m];return(cjr%p);
	}
	inline ll anm(int n,int m){
		if(n<m)return(0);ll cjr=jc[n];cjr*=jcny[n-m];return(cjr%p);
	}
	void ywymain(){
		cin>>n;for(register int i=1;i<n;i++){
			int s,t;cin>>s>>t;add(s,t);add(t,s);
		}dfs(1,0);jc[0]=1;for(register int i=1;i<=n;i++)jc[i]=(jc[i-1]*i)%p;jcny[n]=mi(jc[n],p-2);
		for(register int i=n-1;i>=0;i--)jcny[i]=(jcny[i+1]*(i+1))%p;if(vec.size()==2){
			cout<<(jc[n/2]*jc[n/2])%p<<endl;return;
		}dp[0]=1;int rt=vec[0];efs(rt,0);int tot=0;for(register int i=heads[rt];i;i=memchi[i].nxt){
			tot+=size[memchi[i].dest];for(register int j=tot;j>=0;j--){
				for(register int k=1;k<=min(j,size[memchi[i].dest]);k++){
					ll cjr=dp[j-k];cjr*=cnm(size[memchi[i].dest],k);cjr%=p;cjr*=anm(size[memchi[i].dest],k);
					dp[j]=(dp[j]+cjr)%p;
				}
			}
		}ll ans=0;for(register int i=0;i<=n;i++){
			if(i&1)ans-=dp[i]*jc[n-i],ans%=p,ans+=p,ans%=p;else ans=(ans+dp[i]*jc[n-i])%p;
		}cout<<ans<<endl;
	}
}
int main(){
	ywy::ywymain();return(0);
}
### Prompt

Please create a solution in CPP 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
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#define ll long long
#define p 1000000007
using namespace std;
namespace ywy{
	typedef struct _b{
		int dest;int nxt;
	}bian;bian memchi[1000001];int gn=1,heads[5001];ll jc[5001],jcny[5001];ll dp[5001];
	inline void add(int s,int t){
		memchi[gn].dest=t;memchi[gn].nxt=heads[s];heads[s]=gn;gn++;
	}int size[5001],n;
	inline ll mi(int a,int b){
		ll ans=1,tmp=a;while(b){
			if(b&1)ans=(ans*tmp)%p;tmp=(tmp*tmp)%p;b>>=1;
		}return(ans);
	}vector<int> vec;
	void dfs(int pt,int baba){
		int mx=0;size[pt]=1;for(register int i=heads[pt];i;i=memchi[i].nxt){
			if(memchi[i].dest==baba)continue;dfs(memchi[i].dest,pt);size[pt]+=size[memchi[i].dest];
			mx=max(mx,size[memchi[i].dest]);
		}if(max(mx,n-size[pt])<=n/2)vec.push_back(pt);
	}
	void efs(int pt,int baba){
		size[pt]=1;for(register int i=heads[pt];i;i=memchi[i].nxt){
			if(memchi[i].dest==baba)continue;efs(memchi[i].dest,pt);size[pt]+=size[memchi[i].dest];
		}
	}
	inline ll cnm(int n,int m){
		if(n<m)return(0);ll cjr=jc[n];cjr*=jcny[m];cjr%=p;cjr*=jcny[n-m];return(cjr%p);
	}
	inline ll anm(int n,int m){
		if(n<m)return(0);ll cjr=jc[n];cjr*=jcny[n-m];return(cjr%p);
	}
	void ywymain(){
		cin>>n;for(register int i=1;i<n;i++){
			int s,t;cin>>s>>t;add(s,t);add(t,s);
		}dfs(1,0);jc[0]=1;for(register int i=1;i<=n;i++)jc[i]=(jc[i-1]*i)%p;jcny[n]=mi(jc[n],p-2);
		for(register int i=n-1;i>=0;i--)jcny[i]=(jcny[i+1]*(i+1))%p;if(vec.size()==2){
			cout<<(jc[n/2]*jc[n/2])%p<<endl;return;
		}dp[0]=1;int rt=vec[0];efs(rt,0);int tot=0;for(register int i=heads[rt];i;i=memchi[i].nxt){
			tot+=size[memchi[i].dest];for(register int j=tot;j>=0;j--){
				for(register int k=1;k<=min(j,size[memchi[i].dest]);k++){
					ll cjr=dp[j-k];cjr*=cnm(size[memchi[i].dest],k);cjr%=p;cjr*=anm(size[memchi[i].dest],k);
					dp[j]=(dp[j]+cjr)%p;
				}
			}
		}ll ans=0;for(register int i=0;i<=n;i++){
			if(i&1)ans-=dp[i]*jc[n-i],ans%=p,ans+=p,ans%=p;else ans=(ans+dp[i]*jc[n-i])%p;
		}cout<<ans<<endl;
	}
}
int main(){
	ywy::ywymain();return(0);
}
```