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

vector<int> V[5005];
int sz[5005];
long long dp[5005][5005];
long long fact[10005];long long inv[10005];
long long power(long long a,long long b){
    if(b==0) return 1;
    long long f=power(a,b/2);
    f=(f*f)%MOD;
    if(b%2)
        return (a*f)%MOD;
    return f;
}
long long comb(long long n,long long r){
    if(n<r) return 0;
    if(n==r || r==0 ){
        return 1;
    }

    long long temp=(inv[r]*inv[n-r])%MOD;
    return (fact[n]*temp)%MOD;
}
int dfs(int n,int p=-1){
    sz[n]=1;
    for(int i=0;i<V[n].size();++i){
        if(V[n][i]==p) continue;
        sz[n]+=dfs(V[n][i],n);
    }
    return sz[n];
}
long long dfsx(int n,int si){
    for(int i=0;i<=5000;++i) for(int j=0;j<=5000;++j) dp[i][j]=0;
    for(int i=0;i<=sz[V[n][0]];++i){
        dp[0][i]=(comb(sz[V[n][0]],i)*comb(sz[V[n][0]],i))%MOD;
        dp[0][i]=(dp[0][i]*fact[i])%MOD;
    }
    int tot=sz[V[n][0]];
    for(int i=1;i<V[n].size();++i){
        for(int j=0;j<=tot;++j){
            for(int k=0;k<=sz[V[n][i]];++k){
                long long temp=(comb(sz[V[n][i]],k)*comb(sz[V[n][i]],k))%MOD;
                temp=(temp*fact[k])%MOD;
                dp[i][j+k]=(dp[i][j+k]+dp[i-1][j]*temp)%MOD;
            }
        }
        tot+=sz[V[n][i]];
    }
    long long ans=0;long long an=1;
    for(int i=0;i<=si;++i){
        ans+=an*((fact[si-i]*dp[V[n].size()-1][i]));
        ans%=MOD;an*=-1;
    }
    return ans;

}
vector<int> X;
int main(){
    int n;
    cin >> n;
    fact[0]=inv[0]=1;
    for(long long i=1;i<=10000;++i){
        fact[i]=(i*fact[i-1])%MOD;
        inv[i]=power(fact[i],MOD-2);
    }
    for(int i=1;i<n;++i){
        int a,b;scanf("%d %d",&a,&b);
        V[a].push_back(b);V[b].push_back(a);
    }
    long long ans=0;int flag=0;
    for(int i=1;i<=n;++i){
        X.clear();
        dfs(i);
        for(int j=0;j<V[i].size();++j){
            X.push_back(sz[V[i][j]]);
        }

        sort(X.rbegin(),X.rend());
        int ma=X[0];
        for(int j=1;j<X.size();++j){
            ma-=X[j];
        }
        if(ma>1)
            continue;
        ++flag;
        ans+=dfsx(i,n);
        if(flag==2){
            ans=(fact[n/2]*fact[n/2])%MOD;
            break;
        }
    }
    cout << (ans+MOD)%MOD << 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>
#define MOD 1000000007
using namespace std;

vector<int> V[5005];
int sz[5005];
long long dp[5005][5005];
long long fact[10005];long long inv[10005];
long long power(long long a,long long b){
    if(b==0) return 1;
    long long f=power(a,b/2);
    f=(f*f)%MOD;
    if(b%2)
        return (a*f)%MOD;
    return f;
}
long long comb(long long n,long long r){
    if(n<r) return 0;
    if(n==r || r==0 ){
        return 1;
    }

    long long temp=(inv[r]*inv[n-r])%MOD;
    return (fact[n]*temp)%MOD;
}
int dfs(int n,int p=-1){
    sz[n]=1;
    for(int i=0;i<V[n].size();++i){
        if(V[n][i]==p) continue;
        sz[n]+=dfs(V[n][i],n);
    }
    return sz[n];
}
long long dfsx(int n,int si){
    for(int i=0;i<=5000;++i) for(int j=0;j<=5000;++j) dp[i][j]=0;
    for(int i=0;i<=sz[V[n][0]];++i){
        dp[0][i]=(comb(sz[V[n][0]],i)*comb(sz[V[n][0]],i))%MOD;
        dp[0][i]=(dp[0][i]*fact[i])%MOD;
    }
    int tot=sz[V[n][0]];
    for(int i=1;i<V[n].size();++i){
        for(int j=0;j<=tot;++j){
            for(int k=0;k<=sz[V[n][i]];++k){
                long long temp=(comb(sz[V[n][i]],k)*comb(sz[V[n][i]],k))%MOD;
                temp=(temp*fact[k])%MOD;
                dp[i][j+k]=(dp[i][j+k]+dp[i-1][j]*temp)%MOD;
            }
        }
        tot+=sz[V[n][i]];
    }
    long long ans=0;long long an=1;
    for(int i=0;i<=si;++i){
        ans+=an*((fact[si-i]*dp[V[n].size()-1][i]));
        ans%=MOD;an*=-1;
    }
    return ans;

}
vector<int> X;
int main(){
    int n;
    cin >> n;
    fact[0]=inv[0]=1;
    for(long long i=1;i<=10000;++i){
        fact[i]=(i*fact[i-1])%MOD;
        inv[i]=power(fact[i],MOD-2);
    }
    for(int i=1;i<n;++i){
        int a,b;scanf("%d %d",&a,&b);
        V[a].push_back(b);V[b].push_back(a);
    }
    long long ans=0;int flag=0;
    for(int i=1;i<=n;++i){
        X.clear();
        dfs(i);
        for(int j=0;j<V[i].size();++j){
            X.push_back(sz[V[i][j]]);
        }

        sort(X.rbegin(),X.rend());
        int ma=X[0];
        for(int j=1;j<X.size();++j){
            ma-=X[j];
        }
        if(ma>1)
            continue;
        ++flag;
        ans+=dfsx(i,n);
        if(flag==2){
            ans=(fact[n/2]*fact[n/2])%MOD;
            break;
        }
    }
    cout << (ans+MOD)%MOD << endl;


    return 0;
}

```