#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>

const int MOD = (int)1e9 + 7;
const int kN = 5000 + 5;
std::vector<int> edges[kN];
int n;
bool vis[kN];
int parent[kN];
int sz[kN];
int que[kN];
int balance[kN];

int bfs(int source,int fa = -1) {
    int qf = 0,qe = 0;
    que[qe++] = source;
    parent[source] = fa;
    while (qf != qe) {
        int u = que[qf++];
        sz[u] = 1;
        balance[u] = 0;
        for (int v : edges[u]) {
            if (!vis[v] && parent[u] != v) {
                parent[v] = u;
                que[qe++] = v;
            }
        }
    }
    for (int i = qe - 1; i >= 0; -- i) {
        int u = que[i];
        if (i) {
            sz[parent[u]] += sz[u];
            balance[parent[u]] = std::max(balance[parent[u]],sz[u]);
        }
        balance[u] = std::max(balance[u],qe - sz[u]);
    }
    return qe;
}

int F[kN], Finv[kN], Inv[kN];

int binom(int a, int b)
{
    if (b < 0 || b > a) return 0;
    return F[a] * 1LL * Finv[b] % MOD * Finv[a - b] % MOD;
}

inline void add(int &a, int b)
{
    a += b;
    if (a >= MOD) a -= MOD;
    if (a < 0) a += MOD;
}

int calc(int root)
{
    bfs(root);
    std::vector<int> vec;
    for (int x : edges[root]) {
        vec.emplace_back(sz[x]);
    }

    static int g[2][kN];
    int cur = 0, nex = 1;
    int s = 0;
    g[0][0] = 1;
    for (int x : vec) {
        memset(g[nex], 0, sizeof(g[nex]));
        for (int i = 0; i <= s; ++ i) {
            for (int j = 0; j <= x; ++ j) {
                add(g[nex][i + j], g[cur][i] * 1LL * binom(x, j) % MOD * binom(x, j) % MOD * F[j] % MOD);
            }
        }
        s += x;
        std::swap(cur, nex);
    }
    int ret = 0;
    for (int i = 0; i <= s; ++ i) {
        add(ret, g[cur][i] * 1LL * F[n - i] % MOD * (i % 2 == 0 ? 1 : -1));
    }
    return ret;
}

int main()
{
    Inv[1] = 1;
    for (int i = 2; i < kN; ++ i)
        Inv[i] = (MOD - MOD / i) * 1LL * Inv[MOD % i] % MOD;
    F[0] = 1;
    Finv[0] = 1;
    for (int i = 1; i < kN; ++ i) {
        F[i] = F[i - 1] * 1LL * i % MOD;
        Finv[i] = Finv[i - 1] * 1LL * Inv[i] % MOD;
    }
    scanf("%d", &n);
    for (int i = 0; i < n - 1; ++ i) {
        int a, b;
        scanf("%d%d", &a, &b); a --; b --;
        edges[a].emplace_back(b);
        edges[b].emplace_back(a);
    }
    int root = n;
    {
        std::vector<std::pair<int, int>> vec;
        for (int i = 0; i < n; ++ i) {
            bfs(i);
            vec.emplace_back(balance[i], i);
        }
        std::sort(vec.begin(), vec.end());
        if (vec.size() > 1 && vec[0].first == vec[1].first) {
            printf("%d\n", F[n / 2] * 1LL * F[n / 2] % MOD);
        } else {
            root = vec[0].second;
            printf("%d\n", calc(root));
        }
    }
}

### Prompt

Please formulate 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 <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>

const int MOD = (int)1e9 + 7;
const int kN = 5000 + 5;
std::vector<int> edges[kN];
int n;
bool vis[kN];
int parent[kN];
int sz[kN];
int que[kN];
int balance[kN];

int bfs(int source,int fa = -1) {
    int qf = 0,qe = 0;
    que[qe++] = source;
    parent[source] = fa;
    while (qf != qe) {
        int u = que[qf++];
        sz[u] = 1;
        balance[u] = 0;
        for (int v : edges[u]) {
            if (!vis[v] && parent[u] != v) {
                parent[v] = u;
                que[qe++] = v;
            }
        }
    }
    for (int i = qe - 1; i >= 0; -- i) {
        int u = que[i];
        if (i) {
            sz[parent[u]] += sz[u];
            balance[parent[u]] = std::max(balance[parent[u]],sz[u]);
        }
        balance[u] = std::max(balance[u],qe - sz[u]);
    }
    return qe;
}

int F[kN], Finv[kN], Inv[kN];

int binom(int a, int b)
{
    if (b < 0 || b > a) return 0;
    return F[a] * 1LL * Finv[b] % MOD * Finv[a - b] % MOD;
}

inline void add(int &a, int b)
{
    a += b;
    if (a >= MOD) a -= MOD;
    if (a < 0) a += MOD;
}

int calc(int root)
{
    bfs(root);
    std::vector<int> vec;
    for (int x : edges[root]) {
        vec.emplace_back(sz[x]);
    }

    static int g[2][kN];
    int cur = 0, nex = 1;
    int s = 0;
    g[0][0] = 1;
    for (int x : vec) {
        memset(g[nex], 0, sizeof(g[nex]));
        for (int i = 0; i <= s; ++ i) {
            for (int j = 0; j <= x; ++ j) {
                add(g[nex][i + j], g[cur][i] * 1LL * binom(x, j) % MOD * binom(x, j) % MOD * F[j] % MOD);
            }
        }
        s += x;
        std::swap(cur, nex);
    }
    int ret = 0;
    for (int i = 0; i <= s; ++ i) {
        add(ret, g[cur][i] * 1LL * F[n - i] % MOD * (i % 2 == 0 ? 1 : -1));
    }
    return ret;
}

int main()
{
    Inv[1] = 1;
    for (int i = 2; i < kN; ++ i)
        Inv[i] = (MOD - MOD / i) * 1LL * Inv[MOD % i] % MOD;
    F[0] = 1;
    Finv[0] = 1;
    for (int i = 1; i < kN; ++ i) {
        F[i] = F[i - 1] * 1LL * i % MOD;
        Finv[i] = Finv[i - 1] * 1LL * Inv[i] % MOD;
    }
    scanf("%d", &n);
    for (int i = 0; i < n - 1; ++ i) {
        int a, b;
        scanf("%d%d", &a, &b); a --; b --;
        edges[a].emplace_back(b);
        edges[b].emplace_back(a);
    }
    int root = n;
    {
        std::vector<std::pair<int, int>> vec;
        for (int i = 0; i < n; ++ i) {
            bfs(i);
            vec.emplace_back(balance[i], i);
        }
        std::sort(vec.begin(), vec.end());
        if (vec.size() > 1 && vec[0].first == vec[1].first) {
            printf("%d\n", F[n / 2] * 1LL * F[n / 2] % MOD);
        } else {
            root = vec[0].second;
            printf("%d\n", calc(root));
        }
    }
}

```