// ARC087F.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5050, mod = 1e9 + 7;

int n, head[MAX_N], current, siz[MAX_N], gcnt, fac[MAX_N], fac_inv[MAX_N], gpt, dp[MAX_N];

struct edge
{
    int to, nxt;
} edges[MAX_N << 1];

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

void getSiz(int u, int fa)
{
    int max_part = 0;
    siz[u] = 1;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
        {
            getSiz(edges[i].to, u), max_part = max(max_part, siz[edges[i].to]);
            siz[u] += siz[edges[i].to];
        }
    max_part = max(max_part, n - siz[u]);
    if (max_part <= (n >> 1))
        gcnt++, gpt = u;
}

void dfs(int u, int fa)
{
    siz[u] = 1;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            dfs(edges[i].to, u), siz[u] += siz[edges[i].to];
}

int binomial(int n_, int k_) { return (n_ < k_) ? 0 : 1LL * fac[n_] * fac_inv[k_] % mod * fac_inv[n_ - k_] % mod; }

int permutation(int n_, int k_) { return (n_ < k_) ? 0 : 1LL * fac[n_] * fac_inv[n_ - k_] % mod; }

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int i = 1, u, v; i <= n - 1; i++)
        scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
    getSiz(1, 0);
    for (int i = fac[0] = 1; i < MAX_N; i++)
        fac[i] = 1LL * fac[i - 1] * i % mod;
    fac_inv[0] = fac_inv[1] = 1;
    for (int i = 2; i < MAX_N; i++)
        fac_inv[i] = 1LL * (mod - mod / i) * fac_inv[mod % i] % mod;
    for (int i = 2; i < MAX_N; i++)
        fac_inv[i] = 1LL * fac_inv[i - 1] * fac_inv[i] % mod;
    if (gcnt == 2)
    {
        printf("%lld\n", 1LL * fac[n >> 1] * fac[n >> 1] % mod);
        return 0;
    }
    dfs(gpt, 0), dp[0] = 1;
    int tot_siz = 0;
    for (int i = head[gpt]; i != -1; i = edges[i].nxt)
    {
        tot_siz += siz[edges[i].to];
        for (int j = tot_siz; j >= 0; j--)
            for (int k = 1; k <= min(siz[edges[i].to], j); k++)
            {
                int tmp = 1LL * dp[j - k] * binomial(siz[edges[i].to], k) % mod * permutation(siz[edges[i].to], k) % mod;
                dp[j] = (0LL + dp[j] + tmp) % mod;
            }
    }
    int ans = 0;
    for (int i = 0, opt = 1; i <= n; i++, opt = mod - opt)
        ans = (0LL + ans + 1LL * opt * dp[i] % mod * fac[n - i] % mod) % mod;
    printf("%d\n", ans);
    return 0;
}
### Prompt

Construct a CPP code solution to the problem outlined:

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
// ARC087F.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5050, mod = 1e9 + 7;

int n, head[MAX_N], current, siz[MAX_N], gcnt, fac[MAX_N], fac_inv[MAX_N], gpt, dp[MAX_N];

struct edge
{
    int to, nxt;
} edges[MAX_N << 1];

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

void getSiz(int u, int fa)
{
    int max_part = 0;
    siz[u] = 1;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
        {
            getSiz(edges[i].to, u), max_part = max(max_part, siz[edges[i].to]);
            siz[u] += siz[edges[i].to];
        }
    max_part = max(max_part, n - siz[u]);
    if (max_part <= (n >> 1))
        gcnt++, gpt = u;
}

void dfs(int u, int fa)
{
    siz[u] = 1;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            dfs(edges[i].to, u), siz[u] += siz[edges[i].to];
}

int binomial(int n_, int k_) { return (n_ < k_) ? 0 : 1LL * fac[n_] * fac_inv[k_] % mod * fac_inv[n_ - k_] % mod; }

int permutation(int n_, int k_) { return (n_ < k_) ? 0 : 1LL * fac[n_] * fac_inv[n_ - k_] % mod; }

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int i = 1, u, v; i <= n - 1; i++)
        scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
    getSiz(1, 0);
    for (int i = fac[0] = 1; i < MAX_N; i++)
        fac[i] = 1LL * fac[i - 1] * i % mod;
    fac_inv[0] = fac_inv[1] = 1;
    for (int i = 2; i < MAX_N; i++)
        fac_inv[i] = 1LL * (mod - mod / i) * fac_inv[mod % i] % mod;
    for (int i = 2; i < MAX_N; i++)
        fac_inv[i] = 1LL * fac_inv[i - 1] * fac_inv[i] % mod;
    if (gcnt == 2)
    {
        printf("%lld\n", 1LL * fac[n >> 1] * fac[n >> 1] % mod);
        return 0;
    }
    dfs(gpt, 0), dp[0] = 1;
    int tot_siz = 0;
    for (int i = head[gpt]; i != -1; i = edges[i].nxt)
    {
        tot_siz += siz[edges[i].to];
        for (int j = tot_siz; j >= 0; j--)
            for (int k = 1; k <= min(siz[edges[i].to], j); k++)
            {
                int tmp = 1LL * dp[j - k] * binomial(siz[edges[i].to], k) % mod * permutation(siz[edges[i].to], k) % mod;
                dp[j] = (0LL + dp[j] + tmp) % mod;
            }
    }
    int ans = 0;
    for (int i = 0, opt = 1; i <= n; i++, opt = mod - opt)
        ans = (0LL + ans + 1LL * opt * dp[i] % mod * fac[n - i] % mod) % mod;
    printf("%d\n", ans);
    return 0;
}
```