#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int maxn=5010;
const int mod=1000000007;
struct edge
{
    int t;
    edge *next;
}*con[maxn];
int n,sz[maxn];
ll jie[maxn],inv[maxn],g[2][maxn];
ll ksm(ll a,int b){ll r=1;for(;b;b>>=1){if(b&1) r=r*a%mod;a=a*a%mod;}return r;}
ll A(int a,int b){return jie[a]*inv[a-b]%mod;}
ll C(int a,int b){return A(a,b)*inv[b]%mod;}
void ins(int x,int y)
{
    edge *p=new edge;
    p->t=y;
    p->next=con[x];
    con[x]=p;
}
void getroot(int v,int fa,int &root)
{
    sz[v]=1;    bool flag=1;

    for(edge *p=con[v];p;p=p->next)
        if(p->t!=fa)
        {
            getroot(p->t,v,root);
            sz[v]+=sz[p->t];
            if(sz[p->t]*2>n) flag=0;
        }
    if(sz[v]*2<n) flag=0;
    if(flag) root=(root?-1:v);  
}
ll solve()
{
    int rt=0;
    getroot(1,-1,rt);
    if(rt==-1) return jie[n/2]*jie[n/2]%mod;
    for(edge *p=con[rt];p;p=p->next)
        sz[p->t]=-(sz[p->t]>sz[rt]?n-sz[rt]:sz[p->t]);
    for(int i=1;i<=n;i++)
        sz[i]=(sz[i]>0?0:-sz[i]);       
    int tot=0;
    g[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        tot+=sz[i];
        memset(g[i&1],0,sizeof(g[i&1]));
        for(int j=0;j<=tot;j++)
            for(int k=0;k<=min(sz[i],j);k++)
                g[i&1][j]=(g[i&1][j]+g[(i&1)^1][j-k]*C(sz[i],k)%mod*A(sz[i],k)%mod)%mod;
    }
    ll ans=0;
    for(int i=0,r=1;i<=n;i++,r=-r)
        ans=(ans+(g[n&1][i]*jie[n-i]%mod*r+mod)%mod)%mod;
    return ans; 
}


int main(){
    scanf("%d",&n);
    jie[0]=1;
    for(int i=1;i<=n;i++)
        jie[i]=jie[i-1]*i%mod;
    inv[n]=ksm(jie[n],mod-2);
    for(int i=n-1;i>=0;i--)
        inv[i]=inv[i+1]*(i+1)%mod;  
    //for(int i=0;i<=n;i++)
    //  cout<<jie[i]<<' '<<inv[i]<<endl;    
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        ins(x,y);
        ins(y,x);
    }
    printf("%lld",solve());
    return 0;
}
### Prompt

Your task is to create 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<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int maxn=5010;
const int mod=1000000007;
struct edge
{
    int t;
    edge *next;
}*con[maxn];
int n,sz[maxn];
ll jie[maxn],inv[maxn],g[2][maxn];
ll ksm(ll a,int b){ll r=1;for(;b;b>>=1){if(b&1) r=r*a%mod;a=a*a%mod;}return r;}
ll A(int a,int b){return jie[a]*inv[a-b]%mod;}
ll C(int a,int b){return A(a,b)*inv[b]%mod;}
void ins(int x,int y)
{
    edge *p=new edge;
    p->t=y;
    p->next=con[x];
    con[x]=p;
}
void getroot(int v,int fa,int &root)
{
    sz[v]=1;    bool flag=1;

    for(edge *p=con[v];p;p=p->next)
        if(p->t!=fa)
        {
            getroot(p->t,v,root);
            sz[v]+=sz[p->t];
            if(sz[p->t]*2>n) flag=0;
        }
    if(sz[v]*2<n) flag=0;
    if(flag) root=(root?-1:v);  
}
ll solve()
{
    int rt=0;
    getroot(1,-1,rt);
    if(rt==-1) return jie[n/2]*jie[n/2]%mod;
    for(edge *p=con[rt];p;p=p->next)
        sz[p->t]=-(sz[p->t]>sz[rt]?n-sz[rt]:sz[p->t]);
    for(int i=1;i<=n;i++)
        sz[i]=(sz[i]>0?0:-sz[i]);       
    int tot=0;
    g[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        tot+=sz[i];
        memset(g[i&1],0,sizeof(g[i&1]));
        for(int j=0;j<=tot;j++)
            for(int k=0;k<=min(sz[i],j);k++)
                g[i&1][j]=(g[i&1][j]+g[(i&1)^1][j-k]*C(sz[i],k)%mod*A(sz[i],k)%mod)%mod;
    }
    ll ans=0;
    for(int i=0,r=1;i<=n;i++,r=-r)
        ans=(ans+(g[n&1][i]*jie[n-i]%mod*r+mod)%mod)%mod;
    return ans; 
}


int main(){
    scanf("%d",&n);
    jie[0]=1;
    for(int i=1;i<=n;i++)
        jie[i]=jie[i-1]*i%mod;
    inv[n]=ksm(jie[n],mod-2);
    for(int i=n-1;i>=0;i--)
        inv[i]=inv[i+1]*(i+1)%mod;  
    //for(int i=0;i<=n;i++)
    //  cout<<jie[i]<<' '<<inv[i]<<endl;    
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        ins(x,y);
        ins(y,x);
    }
    printf("%lld",solve());
    return 0;
}
```