#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_map>
#include<iomanip>
#include<bitset>
#define mod 1000000007
using namespace std;
typedef long long ll;
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define mad(a,b) a=(a+b)%mod
#define mul(a,b) a=a*b%mod
#define N 100010
ll fac[N],ivf[N],inv[N];
ll C(ll n,ll k){
    return fac[n]*ivf[k]%mod*ivf[n-k]%mod;
}
ll P(ll n,ll k){
    return fac[n]*ivf[n-k]%mod;
}

ll n;
vector<ll> g[N];
ll dfs(ll x,ll from){
    ll res=1;
    for(auto y:g[x])if(y!=from){
	res+=dfs(y,x);
    }
    return res;
}

ll dp[5010][5010];
int main(){
    fac[0]=ivf[0]=inv[1]=1;
    for(int i=1;i<N;i++){
	if(i>1)inv[i]=(mod-(mod/i*inv[mod%i]%mod))%mod;
	fac[i]=fac[i-1]*i%mod;
	ivf[i]=ivf[i-1]*inv[i]%mod;
    }
    cin>>n;
    for(int i=0;i<n-1;i++){
	ll a,b; cin>>a>>b;
	g[a].push_back(b);
	g[b].push_back(a);
    }
    vector<ll> centroid;
    for(int i=1;i<=n;i++){
	ll ma=0;
	for(auto y:g[i]){
	    chmax(ma,dfs(y,i));
	}
	if(ma<=n/2)centroid.push_back(i);
    }
    if(centroid.size()==2){
	cout<<fac[n/2]*fac[n/2]%mod<<endl;
	return 0;
    }
    vector<ll> siz;
    for(auto y:g[centroid[0]]){
	siz.push_back(dfs(y,centroid[0]));
    }
    for(int i=0;i<5010;i++)dp[0][i]=0;
    dp[0][0]=1;
    for(int i=0;i<siz.size();i++){
	for(int j=0;j<5010;j++)dp[i+1][j]=0;
	for(int j=0;j<5010;j++){
	    for(int k=0;k<=siz[i]&&j+k<5010;k++){
		ll cur=C(siz[i],k)*P(siz[i],k)%mod;
		mad(dp[i+1][j+k],dp[i][j]*cur);
	    }
	}
    }
    ll ans=0;
    for(int i=0;i<=n;i++){
	ll cur=dp[siz.size()][i]*fac[n-i]%mod;
	if(i%2==0)mad(ans,cur);
	else mad(ans,-cur);
    }
    if(ans<0)ans+=mod;
    cout<<ans<<endl;
}


### 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
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_map>
#include<iomanip>
#include<bitset>
#define mod 1000000007
using namespace std;
typedef long long ll;
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define mad(a,b) a=(a+b)%mod
#define mul(a,b) a=a*b%mod
#define N 100010
ll fac[N],ivf[N],inv[N];
ll C(ll n,ll k){
    return fac[n]*ivf[k]%mod*ivf[n-k]%mod;
}
ll P(ll n,ll k){
    return fac[n]*ivf[n-k]%mod;
}

ll n;
vector<ll> g[N];
ll dfs(ll x,ll from){
    ll res=1;
    for(auto y:g[x])if(y!=from){
	res+=dfs(y,x);
    }
    return res;
}

ll dp[5010][5010];
int main(){
    fac[0]=ivf[0]=inv[1]=1;
    for(int i=1;i<N;i++){
	if(i>1)inv[i]=(mod-(mod/i*inv[mod%i]%mod))%mod;
	fac[i]=fac[i-1]*i%mod;
	ivf[i]=ivf[i-1]*inv[i]%mod;
    }
    cin>>n;
    for(int i=0;i<n-1;i++){
	ll a,b; cin>>a>>b;
	g[a].push_back(b);
	g[b].push_back(a);
    }
    vector<ll> centroid;
    for(int i=1;i<=n;i++){
	ll ma=0;
	for(auto y:g[i]){
	    chmax(ma,dfs(y,i));
	}
	if(ma<=n/2)centroid.push_back(i);
    }
    if(centroid.size()==2){
	cout<<fac[n/2]*fac[n/2]%mod<<endl;
	return 0;
    }
    vector<ll> siz;
    for(auto y:g[centroid[0]]){
	siz.push_back(dfs(y,centroid[0]));
    }
    for(int i=0;i<5010;i++)dp[0][i]=0;
    dp[0][0]=1;
    for(int i=0;i<siz.size();i++){
	for(int j=0;j<5010;j++)dp[i+1][j]=0;
	for(int j=0;j<5010;j++){
	    for(int k=0;k<=siz[i]&&j+k<5010;k++){
		ll cur=C(siz[i],k)*P(siz[i],k)%mod;
		mad(dp[i+1][j+k],dp[i][j]*cur);
	    }
	}
    }
    ll ans=0;
    for(int i=0;i<=n;i++){
	ll cur=dp[siz.size()][i]*fac[n-i]%mod;
	if(i%2==0)mad(ans,cur);
	else mad(ans,-cur);
    }
    if(ans<0)ans+=mod;
    cout<<ans<<endl;
}


```