#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int MAX=5040;
const ll MOD=1000000007;
vector<int> conn[MAX],pos;
int par[MAX],cnt[MAX],cntrd,n,chk[MAX];
ll polys[MAX],poly[MAX];
ll fact[MAX],fact_rev[MAX],wow;
int dfs(int x,int p){
    par[x]=p; cnt[x]=1;
    for(int i=0;i<conn[x].size();i++) if(conn[x][i]!=p) cnt[x]+=dfs(conn[x][i],x);
    return cnt[x];
}
int dfs2(int x){
    int t=1;
    if(chk[x]) return 0;
    chk[x]=1;
    for(int i=0;i<conn[x].size();i++) t+=dfs2(conn[x][i]);
    return t;
}
int find_cntrd(int x){
    for(int i=0;i<conn[x].size();i++) if(cnt[conn[x][i]]>n/2&&par[x]!=conn[x][i]) return find_cntrd(conn[x][i]);
    return x;
}
ll power(int x,int y){
    if(y==0) return 1;
    if(y==1) return x;
    ll t=power(x,y/2);
    if(y%2) return (((t*t)%MOD)*x)%MOD;
    return (t*t)%MOD;
}
ll mycount(){
    int tot=0;
    ll fin=0;
    for(int i=0;i<=n;i++) poly[i]=0,polys[i]=0;
    poly[0]=1;
    for(int i=0;i<pos.size();i++){
        tot+=pos[i];
        for(int j=0;j<=pos[i];j++){
            ll t=(fact[pos[i]]*fact_rev[pos[i]-j])%MOD;
            t=(t*t)%MOD; t=(t*fact_rev[j])%MOD;
            for(int k=0;k<=n-j;k++) polys[k+j]+=poly[k]*t,polys[k+j]%=MOD;
        }
        for(int j=0;j<=n;j++) poly[j]=polys[j],polys[j]=0;
    }
    for(int i=0;i<=n;i++) poly[i]*=fact[tot-i],poly[i]%=MOD;
    for(int i=0;i<=n;i++) {
        if(i%2) fin-=poly[i];
        else fin+=poly[i];
        fin+=MOD,fin%=MOD;
    }
    //printf("%lld ",poly[i]);
    return fin;
}
int main(){
    scanf(" %d",&n);
    for(int i=0;i<n-1;i++){
        int t1,t2;
        scanf(" %d %d",&t1,&t2);
        conn[t1].push_back(t2);
        conn[t2].push_back(t1);
    }
    dfs(1,0);
    cntrd=find_cntrd(1); chk[cntrd]=1; fact[0]=1;
    for(int i=0;i<conn[cntrd].size();i++) pos.push_back(dfs2(conn[cntrd][i]));
    //for(int i=0;i<pos.size();i++) printf("%d ",pos[i]);
    for(ll i=1;i<=n;i++) fact[i]=(fact[i-1]*i)%MOD;
    for(ll i=0;i<=n;i++) fact_rev[i]=power(fact[i],MOD-2);
    pos.push_back(1);
    wow+=mycount();
    pos.pop_back();
    wow+=mycount();
    printf("%lld\n",wow%MOD);
}

### Prompt

Create a solution in CPP for 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;
typedef pair<int,int> pii;
typedef long long ll;
const int MAX=5040;
const ll MOD=1000000007;
vector<int> conn[MAX],pos;
int par[MAX],cnt[MAX],cntrd,n,chk[MAX];
ll polys[MAX],poly[MAX];
ll fact[MAX],fact_rev[MAX],wow;
int dfs(int x,int p){
    par[x]=p; cnt[x]=1;
    for(int i=0;i<conn[x].size();i++) if(conn[x][i]!=p) cnt[x]+=dfs(conn[x][i],x);
    return cnt[x];
}
int dfs2(int x){
    int t=1;
    if(chk[x]) return 0;
    chk[x]=1;
    for(int i=0;i<conn[x].size();i++) t+=dfs2(conn[x][i]);
    return t;
}
int find_cntrd(int x){
    for(int i=0;i<conn[x].size();i++) if(cnt[conn[x][i]]>n/2&&par[x]!=conn[x][i]) return find_cntrd(conn[x][i]);
    return x;
}
ll power(int x,int y){
    if(y==0) return 1;
    if(y==1) return x;
    ll t=power(x,y/2);
    if(y%2) return (((t*t)%MOD)*x)%MOD;
    return (t*t)%MOD;
}
ll mycount(){
    int tot=0;
    ll fin=0;
    for(int i=0;i<=n;i++) poly[i]=0,polys[i]=0;
    poly[0]=1;
    for(int i=0;i<pos.size();i++){
        tot+=pos[i];
        for(int j=0;j<=pos[i];j++){
            ll t=(fact[pos[i]]*fact_rev[pos[i]-j])%MOD;
            t=(t*t)%MOD; t=(t*fact_rev[j])%MOD;
            for(int k=0;k<=n-j;k++) polys[k+j]+=poly[k]*t,polys[k+j]%=MOD;
        }
        for(int j=0;j<=n;j++) poly[j]=polys[j],polys[j]=0;
    }
    for(int i=0;i<=n;i++) poly[i]*=fact[tot-i],poly[i]%=MOD;
    for(int i=0;i<=n;i++) {
        if(i%2) fin-=poly[i];
        else fin+=poly[i];
        fin+=MOD,fin%=MOD;
    }
    //printf("%lld ",poly[i]);
    return fin;
}
int main(){
    scanf(" %d",&n);
    for(int i=0;i<n-1;i++){
        int t1,t2;
        scanf(" %d %d",&t1,&t2);
        conn[t1].push_back(t2);
        conn[t2].push_back(t1);
    }
    dfs(1,0);
    cntrd=find_cntrd(1); chk[cntrd]=1; fact[0]=1;
    for(int i=0;i<conn[cntrd].size();i++) pos.push_back(dfs2(conn[cntrd][i]));
    //for(int i=0;i<pos.size();i++) printf("%d ",pos[i]);
    for(ll i=1;i<=n;i++) fact[i]=(fact[i-1]*i)%MOD;
    for(ll i=0;i<=n;i++) fact_rev[i]=power(fact[i],MOD-2);
    pos.push_back(1);
    wow+=mycount();
    pos.pop_back();
    wow+=mycount();
    printf("%lld\n",wow%MOD);
}

```