#include<cstdio>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<iomanip>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
using namespace std;
#define DEBUG(x) cout<<#x<<"="<<x<<endl
#define DEBUG2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<endl
typedef long long ll;
// #define LOCAL
const int MAXN=5e3+10;
const ll MOD=1e9+7;
int N;
vector<int>G[MAXN];
int sz[MAXN];
int maxsz[MAXN];
ll fact[MAXN];
ll C[MAXN][MAXN];
ll dp[MAXN];
ll mult(ll a,ll b)
{
    return a*b%MOD;
}
ll add(ll a,ll b)
{
    return (a+b)%MOD;
}
void init()
{
    fact[0]=1;
    for(int u=1;u<MAXN;u++){
        fact[u]=mult(u,fact[u-1]);
    }
    C[0][0]=1;
    for(int u=1;u<MAXN;u++){
        C[u][0]=C[u][u]=1;
        for(int v=1;v<u;v++){
            C[u][v]=add(C[u-1][v],C[u-1][v-1]);
        }
    }
}
void dfs(int rt,int fa)
{
    sz[rt]=1;
    for(int v:G[rt]){
        if(v==fa)continue;
        dfs(v,rt);
        sz[rt]+=sz[v];
        maxsz[rt]=max(maxsz[rt],sz[v]);
    }
    maxsz[rt]=max(maxsz[rt],N-sz[rt]);
}
void solve()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>N;
    for(int u=0;u<N-1;u++){
        int x,y;
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    init();
    dfs(1,0);
    int f=1;
    for(int u=2;u<=N;u++){
        if(maxsz[f]>maxsz[u]){
            f=u;
        }
    }
    if(N%2==0&&sz[f]==N/2){
        cout<<mult(fact[N/2],fact[N/2]);
        return;
    }
    vector<int>vs;
    for(int v:G[f]){
        if(sz[v]<sz[f])vs.push_back(sz[v]);
    }
    if(f!=1)
        vs.push_back(N-sz[f]);
    int tmp=0;
    dp[0]=1;
    for(int v:vs){
        for(int k=tmp+v;k>=0;k--){
            for(int j=1;j<=v;j++){
                if(j>k)break;
                dp[k]=add(dp[k],mult(mult(dp[k-j],C[v][j]),mult(C[v][j],fact[j])));
            }
        }
        tmp+=v;
    }
    ll ans=0,sg=1;
    for(int u=0;u<N;u++){
        ans=add(ans,mult(mult(dp[u],fact[N-u]),sg));
        sg=mult(sg,MOD-1);
    }
    cout<<ans;
}
int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    solve();
}

### 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<cstdio>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<iomanip>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
using namespace std;
#define DEBUG(x) cout<<#x<<"="<<x<<endl
#define DEBUG2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<endl
typedef long long ll;
// #define LOCAL
const int MAXN=5e3+10;
const ll MOD=1e9+7;
int N;
vector<int>G[MAXN];
int sz[MAXN];
int maxsz[MAXN];
ll fact[MAXN];
ll C[MAXN][MAXN];
ll dp[MAXN];
ll mult(ll a,ll b)
{
    return a*b%MOD;
}
ll add(ll a,ll b)
{
    return (a+b)%MOD;
}
void init()
{
    fact[0]=1;
    for(int u=1;u<MAXN;u++){
        fact[u]=mult(u,fact[u-1]);
    }
    C[0][0]=1;
    for(int u=1;u<MAXN;u++){
        C[u][0]=C[u][u]=1;
        for(int v=1;v<u;v++){
            C[u][v]=add(C[u-1][v],C[u-1][v-1]);
        }
    }
}
void dfs(int rt,int fa)
{
    sz[rt]=1;
    for(int v:G[rt]){
        if(v==fa)continue;
        dfs(v,rt);
        sz[rt]+=sz[v];
        maxsz[rt]=max(maxsz[rt],sz[v]);
    }
    maxsz[rt]=max(maxsz[rt],N-sz[rt]);
}
void solve()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>N;
    for(int u=0;u<N-1;u++){
        int x,y;
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    init();
    dfs(1,0);
    int f=1;
    for(int u=2;u<=N;u++){
        if(maxsz[f]>maxsz[u]){
            f=u;
        }
    }
    if(N%2==0&&sz[f]==N/2){
        cout<<mult(fact[N/2],fact[N/2]);
        return;
    }
    vector<int>vs;
    for(int v:G[f]){
        if(sz[v]<sz[f])vs.push_back(sz[v]);
    }
    if(f!=1)
        vs.push_back(N-sz[f]);
    int tmp=0;
    dp[0]=1;
    for(int v:vs){
        for(int k=tmp+v;k>=0;k--){
            for(int j=1;j<=v;j++){
                if(j>k)break;
                dp[k]=add(dp[k],mult(mult(dp[k-j],C[v][j]),mult(C[v][j],fact[j])));
            }
        }
        tmp+=v;
    }
    ll ans=0,sg=1;
    for(int u=0;u<N;u++){
        ans=add(ans,mult(mult(dp[u],fact[N-u]),sg));
        sg=mult(sg,MOD-1);
    }
    cout<<ans;
}
int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    solve();
}

```