#include<bits/stdc++.h>
using namespace std;
const int maxn=5005;
const int mod=1e9+7;
int n;
int h[maxn],mem;
struct
{
    int v,next;
}e[maxn<<1];
void init()
{
    memset(h,-1,sizeof(h));
    mem=0;
}
void add(int u,int v)
{
    e[mem].v=v;
    e[mem].next=h[u];
    h[u]=mem++;
    e[mem].v=u;
    e[mem].next=h[v];
    h[v]=mem++;
}
long long fac[maxn];
long long inv[maxn];
void pre()
{
    fac[0]=fac[1]=inv[1]=inv[0]=1;
    for(int i=2;i<maxn;i++)
    {
        fac[i]=fac[i-1]*i%mod;
        inv[i]=mod-mod/i*inv[mod%i]%mod;
    }
    for(int i=2;i<maxn;i++)
        inv[i]=inv[i]*inv[i-1]%mod;
}
long long C(int a,int b)
{
    if(b<0||b>a) return 0;
    return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
long long A(int a,int b)
{
    if(b<0||b>a) return 0;
    return fac[a]*inv[a-b]%mod;
}
int sz[maxn];
vector<int> q;
void dfs(int u,int fa)
{
    sz[u]=1;
    int mx=0;
    for(int i=h[u];i+1;i=e[i].next)
    {
        int v=e[i].v;
        if(v==fa) continue;
        dfs(v,u);
        sz[u]+=sz[v];
        mx=max(mx,sz[v]);
    }
    mx=max(mx,n-sz[u]);
    if(mx<=n/2){
        q.clear();
        for(int i=h[u];i+1;i=e[i].next)
        {
            int v=e[i].v;
            if(v==fa) continue;
            q.push_back(sz[v]);
        }
        q.push_back(n-sz[u]);
    }
}
long long dp[2][maxn];
int main()
{
    init();
    pre();
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    dfs(1,1);
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    int cnt=0;
    int now=1;
    for(int i=0;i<q.size();i++)
    {
        int tsz=q[i];
        cnt=cnt^1;
        memset(dp[cnt],0,sizeof(dp[cnt]));
        for(int j=0;j<now;j++)
        {
            for(int k=0;k<=tsz;k++)
            {
                dp[cnt][j+k]=(dp[cnt][j+k]+dp[cnt^1][j]*C(tsz,k)%mod*A(tsz,k))%mod;
            }
        }
        now+=tsz;
    }
    long long ans=0;
    for(int i=0;i<now;i++)
    {
        int fu;
        if(i&1) fu=-1;
        else fu=1;
        ans=(ans+fu*dp[cnt][i]*fac[n-i])%mod;
    }
    printf("%lld\n",(ans%mod+mod)%mod);
    return 0;
}

### 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<bits/stdc++.h>
using namespace std;
const int maxn=5005;
const int mod=1e9+7;
int n;
int h[maxn],mem;
struct
{
    int v,next;
}e[maxn<<1];
void init()
{
    memset(h,-1,sizeof(h));
    mem=0;
}
void add(int u,int v)
{
    e[mem].v=v;
    e[mem].next=h[u];
    h[u]=mem++;
    e[mem].v=u;
    e[mem].next=h[v];
    h[v]=mem++;
}
long long fac[maxn];
long long inv[maxn];
void pre()
{
    fac[0]=fac[1]=inv[1]=inv[0]=1;
    for(int i=2;i<maxn;i++)
    {
        fac[i]=fac[i-1]*i%mod;
        inv[i]=mod-mod/i*inv[mod%i]%mod;
    }
    for(int i=2;i<maxn;i++)
        inv[i]=inv[i]*inv[i-1]%mod;
}
long long C(int a,int b)
{
    if(b<0||b>a) return 0;
    return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
long long A(int a,int b)
{
    if(b<0||b>a) return 0;
    return fac[a]*inv[a-b]%mod;
}
int sz[maxn];
vector<int> q;
void dfs(int u,int fa)
{
    sz[u]=1;
    int mx=0;
    for(int i=h[u];i+1;i=e[i].next)
    {
        int v=e[i].v;
        if(v==fa) continue;
        dfs(v,u);
        sz[u]+=sz[v];
        mx=max(mx,sz[v]);
    }
    mx=max(mx,n-sz[u]);
    if(mx<=n/2){
        q.clear();
        for(int i=h[u];i+1;i=e[i].next)
        {
            int v=e[i].v;
            if(v==fa) continue;
            q.push_back(sz[v]);
        }
        q.push_back(n-sz[u]);
    }
}
long long dp[2][maxn];
int main()
{
    init();
    pre();
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    dfs(1,1);
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    int cnt=0;
    int now=1;
    for(int i=0;i<q.size();i++)
    {
        int tsz=q[i];
        cnt=cnt^1;
        memset(dp[cnt],0,sizeof(dp[cnt]));
        for(int j=0;j<now;j++)
        {
            for(int k=0;k<=tsz;k++)
            {
                dp[cnt][j+k]=(dp[cnt][j+k]+dp[cnt^1][j]*C(tsz,k)%mod*A(tsz,k))%mod;
            }
        }
        now+=tsz;
    }
    long long ans=0;
    for(int i=0;i<now;i++)
    {
        int fu;
        if(i&1) fu=-1;
        else fu=1;
        ans=(ans+fu*dp[cnt][i]*fac[n-i])%mod;
    }
    printf("%lld\n",(ans%mod+mod)%mod);
    return 0;
}

```