#include<bits/stdc++.h>
#define N 5009
#define P pair<int,int>
#define mm make_pair
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int tot,head[N],dp[N],root2,root1,b[N],tp,n,size[N];
ll f[N][N],jie[N],ni[N];
int mx,now;
inline ll rd(){
    ll x=0;char c=getchar();bool f=0;
    while(!isdigit(c)){if(c=='-')f=1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
inline ll pf(ll x){return x*x%mod;}
inline void MOD(ll &x){x=x>=mod?x-mod:x;}
inline ll C(int n,int m){return jie[n]*ni[m]%mod*ni[n-m]%mod;}
inline ll A(int n,int m){return jie[n]*ni[n-m]%mod;}
struct edge{int n,to;}e[N<<1];
inline void add(int u,int v){e[++tot].n=head[u];e[tot].to=v;head[u]=tot;}
inline ll power(ll x,ll y){
    ll ans=1;
    while(y){
        if(y&1)ans=ans*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return ans;
}
void getroot(int u,int fa){
    size[u]=1;dp[u]=0;
    for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa){
        int v=e[i].to;
        getroot(v,u);
        size[u]+=size[v];
        dp[u]=max(dp[u],size[v]);
    }
    dp[u]=max(dp[u],n-size[u]);
    if(dp[u]<mx){root1=u;root2=0;mx=dp[u];}
    else if(dp[u]==mx)root2=u;
}
int main(){
    mx=1e9;
    n=rd();
    jie[0]=1;
    for(int i=1;i<=n;++i)jie[i]=jie[i-1]*i%mod;ni[n]=power(jie[n],mod-2);
    for(int i=n-1;i>=0;--i)ni[i]=ni[i+1]*(i+1)%mod;
    int x,y;
    for(int i=1;i<n;++i){
        x=rd();y=rd();
        add(x,y);add(y,x);
    }
    getroot(1,0);
    if(root2){
      printf("%lld\n",pf(jie[n/2]));
      return 0;
    }
    for(int i=head[root1];i;i=e[i].n){
        int v=e[i].to;
        if(size[v]>size[root1])size[v]=n-size[root1];
        b[++tp]=size[v];
    }
    f[1][0]=1;
    int now=1,pre=0;
    int siz=0;
    for(int i=1;i<=tp;++i){
        swap(now,pre);
        siz+=b[i];
        memset(f[now],0,sizeof(f[now]));
        for(int j=0;j<=siz;++j)
            for(int k=0;k<=min(j,b[i]);++k)
                MOD(f[now][j]+=f[now^1][j-k]*C(b[i],k)%mod*A(b[i],k)%mod);
    }
    ll ans=0;
    for(int i=0;i<=siz;++i){
        if(i&1)MOD(ans+=f[now][i]*jie[n-i]%mod*(mod-1)%mod);
        else MOD(ans+=f[now][i]*jie[n-i]%mod);
    }
    cout<<ans;
    return 0;
}
### Prompt

Please formulate 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 N 5009
#define P pair<int,int>
#define mm make_pair
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int tot,head[N],dp[N],root2,root1,b[N],tp,n,size[N];
ll f[N][N],jie[N],ni[N];
int mx,now;
inline ll rd(){
    ll x=0;char c=getchar();bool f=0;
    while(!isdigit(c)){if(c=='-')f=1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
inline ll pf(ll x){return x*x%mod;}
inline void MOD(ll &x){x=x>=mod?x-mod:x;}
inline ll C(int n,int m){return jie[n]*ni[m]%mod*ni[n-m]%mod;}
inline ll A(int n,int m){return jie[n]*ni[n-m]%mod;}
struct edge{int n,to;}e[N<<1];
inline void add(int u,int v){e[++tot].n=head[u];e[tot].to=v;head[u]=tot;}
inline ll power(ll x,ll y){
    ll ans=1;
    while(y){
        if(y&1)ans=ans*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return ans;
}
void getroot(int u,int fa){
    size[u]=1;dp[u]=0;
    for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa){
        int v=e[i].to;
        getroot(v,u);
        size[u]+=size[v];
        dp[u]=max(dp[u],size[v]);
    }
    dp[u]=max(dp[u],n-size[u]);
    if(dp[u]<mx){root1=u;root2=0;mx=dp[u];}
    else if(dp[u]==mx)root2=u;
}
int main(){
    mx=1e9;
    n=rd();
    jie[0]=1;
    for(int i=1;i<=n;++i)jie[i]=jie[i-1]*i%mod;ni[n]=power(jie[n],mod-2);
    for(int i=n-1;i>=0;--i)ni[i]=ni[i+1]*(i+1)%mod;
    int x,y;
    for(int i=1;i<n;++i){
        x=rd();y=rd();
        add(x,y);add(y,x);
    }
    getroot(1,0);
    if(root2){
      printf("%lld\n",pf(jie[n/2]));
      return 0;
    }
    for(int i=head[root1];i;i=e[i].n){
        int v=e[i].to;
        if(size[v]>size[root1])size[v]=n-size[root1];
        b[++tp]=size[v];
    }
    f[1][0]=1;
    int now=1,pre=0;
    int siz=0;
    for(int i=1;i<=tp;++i){
        swap(now,pre);
        siz+=b[i];
        memset(f[now],0,sizeof(f[now]));
        for(int j=0;j<=siz;++j)
            for(int k=0;k<=min(j,b[i]);++k)
                MOD(f[now][j]+=f[now^1][j-k]*C(b[i],k)%mod*A(b[i],k)%mod);
    }
    ll ans=0;
    for(int i=0;i<=siz;++i){
        if(i&1)MOD(ans+=f[now][i]*jie[n-i]%mod*(mod-1)%mod);
        else MOD(ans+=f[now][i]*jie[n-i]%mod);
    }
    cout<<ans;
    return 0;
}
```