#include<bits/stdc++.h>
using namespace std;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int mod=1000000007;
inline void add(int &a,int b){
    a+=b;
    if(a>=mod)a-=mod;
}
int mpow(int n,int m){
    int ret=1;
    while(m){
        if(m&1)ret=ret*n%mod;
        n=n*n%mod;
        m>>=1;
    }
    return ret;
}
const int FACT_SIZE=1111111;
int fact[FACT_SIZE];
int inv[FACT_SIZE];
struct fact_exec{
    fact_exec(){
        fact[0]=1;
        for(int i=1;i<FACT_SIZE;i++)fact[i]=fact[i-1]*i%mod;
        inv[FACT_SIZE-1]=mpow(fact[FACT_SIZE-1],mod-2);
        for(int i=FACT_SIZE-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
    }
}factexec;
int nCk(int n,int k){
    return fact[n]*inv[k]%mod*inv[n-k]%mod;
}
int nPk(int n,int k){
    return fact[n]*inv[n-k]%mod;
}


int N;
vint G[5555];
int sz[5555];

pint dfs(int v,int p){
    sz[v]=1;
    int m=0;

    pint ret(INT_MAX,-1);
    for(auto u:G[v]){
        if(u==p)continue;
        chmin(ret,dfs(u,v));
        sz[v]+=sz[u];
        chmax(m,sz[u]);
    }
    chmax(m,N-sz[v]);
    chmin(ret,pint(m,v));
    return ret;
}

int dp[2][5555];

signed main(){
    cin>>N;
    rep(i,N-1){
        int a,b;
        cin>>a>>b;
        a--;b--;
        G[a].pb(b);G[b].pb(a);
    }

    int c=dfs(0,-1).se;
    dfs(c,-1);

    vint v;
    for(auto u:G[c])v.pb(sz[u]);

    int n=v.size();
    dp[0][0]=1;
    rep(i,n){
        rep(j,N+1){
            rep(k,v[i]+1){
                if(j+k>N)break;
                int tmp=nCk(v[i],k)*nCk(v[i],k)%mod;
                tmp=tmp*fact[k]%mod;
                add(dp[(i+1)&1][j+k],dp[i&1][j]*tmp%mod);
            }
            dp[i&1][j]=0;
        }
    }

    int ans=0;
    for(int i=0;i<N;i++){
        int tmp=dp[n&1][i];
        tmp=tmp*fact[N-i]%mod;
        if(i&1)add(ans,mod-tmp);
        else add(ans,tmp);
    }
    cout<<ans<<endl;
    return 0;
}

### Prompt

Please provide a cpp coded solution 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<bits/stdc++.h>
using namespace std;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int mod=1000000007;
inline void add(int &a,int b){
    a+=b;
    if(a>=mod)a-=mod;
}
int mpow(int n,int m){
    int ret=1;
    while(m){
        if(m&1)ret=ret*n%mod;
        n=n*n%mod;
        m>>=1;
    }
    return ret;
}
const int FACT_SIZE=1111111;
int fact[FACT_SIZE];
int inv[FACT_SIZE];
struct fact_exec{
    fact_exec(){
        fact[0]=1;
        for(int i=1;i<FACT_SIZE;i++)fact[i]=fact[i-1]*i%mod;
        inv[FACT_SIZE-1]=mpow(fact[FACT_SIZE-1],mod-2);
        for(int i=FACT_SIZE-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
    }
}factexec;
int nCk(int n,int k){
    return fact[n]*inv[k]%mod*inv[n-k]%mod;
}
int nPk(int n,int k){
    return fact[n]*inv[n-k]%mod;
}


int N;
vint G[5555];
int sz[5555];

pint dfs(int v,int p){
    sz[v]=1;
    int m=0;

    pint ret(INT_MAX,-1);
    for(auto u:G[v]){
        if(u==p)continue;
        chmin(ret,dfs(u,v));
        sz[v]+=sz[u];
        chmax(m,sz[u]);
    }
    chmax(m,N-sz[v]);
    chmin(ret,pint(m,v));
    return ret;
}

int dp[2][5555];

signed main(){
    cin>>N;
    rep(i,N-1){
        int a,b;
        cin>>a>>b;
        a--;b--;
        G[a].pb(b);G[b].pb(a);
    }

    int c=dfs(0,-1).se;
    dfs(c,-1);

    vint v;
    for(auto u:G[c])v.pb(sz[u]);

    int n=v.size();
    dp[0][0]=1;
    rep(i,n){
        rep(j,N+1){
            rep(k,v[i]+1){
                if(j+k>N)break;
                int tmp=nCk(v[i],k)*nCk(v[i],k)%mod;
                tmp=tmp*fact[k]%mod;
                add(dp[(i+1)&1][j+k],dp[i&1][j]*tmp%mod);
            }
            dp[i&1][j]=0;
        }
    }

    int ans=0;
    for(int i=0;i<N;i++){
        int tmp=dp[n&1][i];
        tmp=tmp*fact[N-i]%mod;
        if(i&1)add(ans,mod-tmp);
        else add(ans,tmp);
    }
    cout<<ans<<endl;
    return 0;
}

```