#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 5003;
const ll MOD = 1e9+7;
ll fac[5010], fnv[5010];
ll D[5010][5010];
int ni[5010], sz[5010];
int n;
vector<int> lis[5010];

int idfs(int here, int p) {
    sz[here] = 1;
    for (int &there : lis[here]) {
        if (there==p) continue;
        sz[here] += idfs(there,here);
    }
    return sz[here];
}

int cdfs(int here, int p) {
    for (int &there :lis[here]) {
        if (there==p) continue;
        if (sz[there]>n/2) return cdfs(there,here);
    }
    return here;
}

ll power(ll a, ll n) {
    if (!n) return 1;
    ll t = power(a,n/2);
    return t*t%MOD*((n&1)?a:1)%MOD;
}

void init() {
    int i;
    fac[0] = 1;
    for (i=1;i<MAXN;i++) fac[i]=fac[i-1]*i%MOD;
    for (i=0;i<MAXN;i++) fnv[i]=power(fac[i],MOD-2);
}

ll calc(int p) {
    int i, j, k, s = ni[0];
    for (i=0;i<=ni[0];i++) D[0][i] = fnv[ni[0]-i]*fnv[ni[0]-i]%MOD*fnv[i]%MOD;
    for (i=1;i<p;i++) {
        s += ni[i];
        for (j=0;j<=s;j++) {
            D[i][j] = 0;
            for (k=0;k<=min(j,ni[i]);k++) D[i][j] += D[i-1][j-k]*fnv[ni[i]-k]%MOD*fnv[ni[i]-k]%MOD*fnv[k]%MOD;
            D[i][j]%=MOD;
        }
    }
    int q = 1;
    ll res = 0, val = 1;
    for (i=0;i<p;i++) val = val*fac[ni[i]]%MOD*fac[ni[i]]%MOD;
    for (i=0;i<=s;i++,q=-q) {
        res = (res+q*D[p-1][i]*fac[s-i]%MOD)%MOD;
    }
    return (res*val%MOD+MOD)%MOD;
}

int main() {
    scanf("%d",&n);
    int i;

    init();
    for (i=0;i<n-1;i++){
        int a, b;
        scanf("%d%d",&a,&b);--a;--b;
        lis[a].push_back(b);lis[b].push_back(a);
    }
    idfs(0,-1);
    int cen = cdfs(0,-1);
    idfs(cen,-1);
    if (n%2==0) {
        bool flag = 0;
        for (int &there : lis[cen]) {
            if (sz[there]==n/2) {
                flag = 1;
                break;
            }
        }
        if (flag) {
            printf("%lld\n",fac[n/2]*fac[n/2]%MOD);
            return 0;
        }
    }
    int p = 0;
    for (int &there : lis[cen]) ni[p++] = sz[there];
    ni[p++] = 1;
    printf("%lld\n",(calc(p-1)+calc(p))%MOD);

    return 0;
}

### Prompt

Your challenge is to write 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 <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 5003;
const ll MOD = 1e9+7;
ll fac[5010], fnv[5010];
ll D[5010][5010];
int ni[5010], sz[5010];
int n;
vector<int> lis[5010];

int idfs(int here, int p) {
    sz[here] = 1;
    for (int &there : lis[here]) {
        if (there==p) continue;
        sz[here] += idfs(there,here);
    }
    return sz[here];
}

int cdfs(int here, int p) {
    for (int &there :lis[here]) {
        if (there==p) continue;
        if (sz[there]>n/2) return cdfs(there,here);
    }
    return here;
}

ll power(ll a, ll n) {
    if (!n) return 1;
    ll t = power(a,n/2);
    return t*t%MOD*((n&1)?a:1)%MOD;
}

void init() {
    int i;
    fac[0] = 1;
    for (i=1;i<MAXN;i++) fac[i]=fac[i-1]*i%MOD;
    for (i=0;i<MAXN;i++) fnv[i]=power(fac[i],MOD-2);
}

ll calc(int p) {
    int i, j, k, s = ni[0];
    for (i=0;i<=ni[0];i++) D[0][i] = fnv[ni[0]-i]*fnv[ni[0]-i]%MOD*fnv[i]%MOD;
    for (i=1;i<p;i++) {
        s += ni[i];
        for (j=0;j<=s;j++) {
            D[i][j] = 0;
            for (k=0;k<=min(j,ni[i]);k++) D[i][j] += D[i-1][j-k]*fnv[ni[i]-k]%MOD*fnv[ni[i]-k]%MOD*fnv[k]%MOD;
            D[i][j]%=MOD;
        }
    }
    int q = 1;
    ll res = 0, val = 1;
    for (i=0;i<p;i++) val = val*fac[ni[i]]%MOD*fac[ni[i]]%MOD;
    for (i=0;i<=s;i++,q=-q) {
        res = (res+q*D[p-1][i]*fac[s-i]%MOD)%MOD;
    }
    return (res*val%MOD+MOD)%MOD;
}

int main() {
    scanf("%d",&n);
    int i;

    init();
    for (i=0;i<n-1;i++){
        int a, b;
        scanf("%d%d",&a,&b);--a;--b;
        lis[a].push_back(b);lis[b].push_back(a);
    }
    idfs(0,-1);
    int cen = cdfs(0,-1);
    idfs(cen,-1);
    if (n%2==0) {
        bool flag = 0;
        for (int &there : lis[cen]) {
            if (sz[there]==n/2) {
                flag = 1;
                break;
            }
        }
        if (flag) {
            printf("%lld\n",fac[n/2]*fac[n/2]%MOD);
            return 0;
        }
    }
    int p = 0;
    for (int &there : lis[cen]) ni[p++] = sz[there];
    ni[p++] = 1;
    printf("%lld\n",(calc(p-1)+calc(p))%MOD);

    return 0;
}

```