#include <algorithm>
#include <cstring>
#include <iostream>
#define MAXN 5010
#define MOD 1000000007
int head[MAXN], to[MAXN << 1], next[MAXN << 1], tot = 0;
inline void $(int u, int v) {
    next[tot] = head[u], to[tot] = v, head[u] = tot++;
    next[tot] = head[v], to[tot] = u, head[v] = tot++;
}
int n, size[MAXN], sf[MAXN], root, rnt;
void G(int x, int fa) {
    size[x] = 1;
    for (int i = head[x]; ~i; i = next[i]) {
        if (to[i] == fa) continue;
        G(to[i], x);
        size[x] += size[to[i]];
        sf[x] = std::max(sf[x], size[to[i]]);
    }
    sf[x] = std::max(sf[x], n - size[x]);
    if (sf[x] < sf[root])
        root = x, rnt = 1;
    else if (sf[x] == sf[root])
        rnt = 2;
}
long long frc[MAXN], inv[MAXN], f[2][MAXN];
inline long long fpow(long long x, int p) {
    long long r = 1;
    while (p) {
        if (p & 1) (r *= x) %= MOD;
        (x *= x) %= MOD;
        p >>= 1;
    }
    return r;
}
inline long long C(int n, int m) {
    return frc[n] * inv[m] % MOD * inv[n - m] % MOD;
}
int main() {
    frc[0] = 1;
    for (int i = 1; i < MAXN; i++) frc[i] = frc[i - 1] * i % MOD;
    inv[MAXN - 1] = fpow(frc[MAXN - 1], MOD - 2);
    for (int i = MAXN - 1; i; i--) inv[i - 1] = inv[i] * i % MOD;
    std::cin >> n;
    memset(head, -1, sizeof(head));
    for (int i = 1; i < n; i++) {
        int u, v;
        std::cin >> u >> v;
        $(u, v);
    }
    sf[root = 0] = n + 1;
    G(1, 0);
    if (rnt > 1) {
        std::cout << frc[size[1] >> 1] * frc[size[1] >> 1] % MOD << std::endl;
        return 0;
    }
    G(root, 0);
    int now = 0, pre = 1;
    f[pre][0] = 1;
    for (int i = head[root]; ~i; i = next[i]) {
        memset(f[now], 0, sizeof(f[now]));
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= size[to[i]]; k++)
                (f[now][j + k] += f[pre][j] * C(size[to[i]], k) % MOD *
                                  C(size[to[i]], k) % MOD * frc[k] % MOD) %=
                    MOD;
        }
        std::swap(pre, now);
    }
    long long ans = 0;
    for (int i = 0; i <= n; i++)
        (ans -= f[pre][i] * (i & 1 ? 1 : -1) * frc[n - i]) %= MOD;
    std::cout << ((ans += MOD) %= MOD) << std::endl;
    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 <algorithm>
#include <cstring>
#include <iostream>
#define MAXN 5010
#define MOD 1000000007
int head[MAXN], to[MAXN << 1], next[MAXN << 1], tot = 0;
inline void $(int u, int v) {
    next[tot] = head[u], to[tot] = v, head[u] = tot++;
    next[tot] = head[v], to[tot] = u, head[v] = tot++;
}
int n, size[MAXN], sf[MAXN], root, rnt;
void G(int x, int fa) {
    size[x] = 1;
    for (int i = head[x]; ~i; i = next[i]) {
        if (to[i] == fa) continue;
        G(to[i], x);
        size[x] += size[to[i]];
        sf[x] = std::max(sf[x], size[to[i]]);
    }
    sf[x] = std::max(sf[x], n - size[x]);
    if (sf[x] < sf[root])
        root = x, rnt = 1;
    else if (sf[x] == sf[root])
        rnt = 2;
}
long long frc[MAXN], inv[MAXN], f[2][MAXN];
inline long long fpow(long long x, int p) {
    long long r = 1;
    while (p) {
        if (p & 1) (r *= x) %= MOD;
        (x *= x) %= MOD;
        p >>= 1;
    }
    return r;
}
inline long long C(int n, int m) {
    return frc[n] * inv[m] % MOD * inv[n - m] % MOD;
}
int main() {
    frc[0] = 1;
    for (int i = 1; i < MAXN; i++) frc[i] = frc[i - 1] * i % MOD;
    inv[MAXN - 1] = fpow(frc[MAXN - 1], MOD - 2);
    for (int i = MAXN - 1; i; i--) inv[i - 1] = inv[i] * i % MOD;
    std::cin >> n;
    memset(head, -1, sizeof(head));
    for (int i = 1; i < n; i++) {
        int u, v;
        std::cin >> u >> v;
        $(u, v);
    }
    sf[root = 0] = n + 1;
    G(1, 0);
    if (rnt > 1) {
        std::cout << frc[size[1] >> 1] * frc[size[1] >> 1] % MOD << std::endl;
        return 0;
    }
    G(root, 0);
    int now = 0, pre = 1;
    f[pre][0] = 1;
    for (int i = head[root]; ~i; i = next[i]) {
        memset(f[now], 0, sizeof(f[now]));
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= size[to[i]]; k++)
                (f[now][j + k] += f[pre][j] * C(size[to[i]], k) % MOD *
                                  C(size[to[i]], k) % MOD * frc[k] % MOD) %=
                    MOD;
        }
        std::swap(pre, now);
    }
    long long ans = 0;
    for (int i = 0; i <= n; i++)
        (ans -= f[pre][i] * (i & 1 ? 1 : -1) * frc[n - i]) %= MOD;
    std::cout << ((ans += MOD) %= MOD) << std::endl;
    return 0;
}
```