#include <cstdio>
#define FOR(i, l, r) for(int i = l; i <= r; ++i)

using namespace std;

typedef long long ll;
const int N = 5010;
const int mod = 1e9 + 7;

struct edge{int to, next;} e[N << 1];
ll c[N][N], f[N][N], fac[N], ans;
int Size[N], size[N], head[N], rt[10], fa[N], n, cnt, x, y, tot;

void ins(int x, int y)
{
    e[++cnt].to = y; e[cnt].next = head[x]; head[x] = cnt;

}
void pre_work()
{
    fac[0] = 1; FOR(i, 1, n) fac[i] = fac[i - 1] * i % mod;
    FOR(i, 0, n)
    {
        c[i][0] = 1;
        FOR(j, 1, i) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    }
}

void dfs(int x, int y)
{
    size[x] = 1; bool fl = 1;
    for(int i = head[x]; i; i = e[i].next)
        if (e[i].to != y)
        {
            dfs(e[i].to, x); fa[e[i].to] = x;
            if (size[e[i].to] > n / 2) fl = 0;
            size[x] += size[e[i].to];
        }
    if (n - size[x] > n / 2) fl = 0;
    if (fl) rt[++tot] = x;
}

int main()
{
    scanf("%d", &n);
    FOR(i, 2, n)
    {
        scanf("%d%d", &x, &y);
        ins(x, y); ins(y, x);
    }
    pre_work();
    dfs(1, 0);
    if (tot == 2) printf("%lld\n", fac[n / 2] * fac[n / 2] % mod);
    else
    {
        f[0][0] = 1; ll now = 1;
        Size[tot = 1] = n - size[rt[1]];
        for(int i = head[rt[1]]; i; i = e[i].next)
            if (e[i].to != fa[rt[1]]) Size[++tot] = size[e[i].to];
        FOR(i, 1, tot) FOR(j, 0, Size[i]) FOR(k, 0, n)
            (f[i][k + j] += f[i - 1][k] * c[Size[i]][j] % mod * c[Size[i]][j] % mod * fac[j]) %= mod;
        FOR(i, 0, n - 1) ans = (ans + mod + now * f[tot][i] * fac[n - i] % mod) % mod, now = -now;
        printf("%lld\n", ans);
    }
    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 <cstdio>
#define FOR(i, l, r) for(int i = l; i <= r; ++i)

using namespace std;

typedef long long ll;
const int N = 5010;
const int mod = 1e9 + 7;

struct edge{int to, next;} e[N << 1];
ll c[N][N], f[N][N], fac[N], ans;
int Size[N], size[N], head[N], rt[10], fa[N], n, cnt, x, y, tot;

void ins(int x, int y)
{
    e[++cnt].to = y; e[cnt].next = head[x]; head[x] = cnt;

}
void pre_work()
{
    fac[0] = 1; FOR(i, 1, n) fac[i] = fac[i - 1] * i % mod;
    FOR(i, 0, n)
    {
        c[i][0] = 1;
        FOR(j, 1, i) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    }
}

void dfs(int x, int y)
{
    size[x] = 1; bool fl = 1;
    for(int i = head[x]; i; i = e[i].next)
        if (e[i].to != y)
        {
            dfs(e[i].to, x); fa[e[i].to] = x;
            if (size[e[i].to] > n / 2) fl = 0;
            size[x] += size[e[i].to];
        }
    if (n - size[x] > n / 2) fl = 0;
    if (fl) rt[++tot] = x;
}

int main()
{
    scanf("%d", &n);
    FOR(i, 2, n)
    {
        scanf("%d%d", &x, &y);
        ins(x, y); ins(y, x);
    }
    pre_work();
    dfs(1, 0);
    if (tot == 2) printf("%lld\n", fac[n / 2] * fac[n / 2] % mod);
    else
    {
        f[0][0] = 1; ll now = 1;
        Size[tot = 1] = n - size[rt[1]];
        for(int i = head[rt[1]]; i; i = e[i].next)
            if (e[i].to != fa[rt[1]]) Size[++tot] = size[e[i].to];
        FOR(i, 1, tot) FOR(j, 0, Size[i]) FOR(k, 0, n)
            (f[i][k + j] += f[i - 1][k] * c[Size[i]][j] % mod * c[Size[i]][j] % mod * fac[j]) %= mod;
        FOR(i, 0, n - 1) ans = (ans + mod + now * f[tot][i] * fac[n - i] % mod) % mod, now = -now;
        printf("%lld\n", ans);
    }
    return 0;
}

```