#include <bits/stdc++.h>
namespace fdata
{
inline char nextchar()
{
    static const int BS = 1 << 21;
    static char buf[BS], *st, *ed;
    if (st == ed)
        ed = buf + fread(st = buf, 1, BS, stdin);
    return st == ed ? -1 : *st++;
}
template <typename T>
inline T poread()
{
    T ret = 0;
    char ch;
    while (!isdigit(ch = nextchar()))
        ;

    do
        ret = ret * 10 + ch - '0';
    while (isdigit(ch = nextchar()));
    return ret;
}
} // namespace fdata
using namespace std;
using fdata::poread;
#define int long long
const int MAXN = 5e3 + 1;
const int MAXM = 1e7 + 1;
const int MOD = 1e9 + 7;
int n;
int ver[MAXM], nxt[MAXM], head[MAXN], tot;
int siz[MAXN];
long long jc[MAXN], jcny[MAXN];
long long f[MAXN];
vector<int> vet;
inline void add(int x, int y)
{
    ver[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
}
template <typename T>
inline T power(T a, int b)
{
    T ans = 1 % MOD;
    for (; b; b >>= 1)
    {
        if (b & 1)
            ans = (long long)ans * a % MOD;
        a = (long long)a * a % MOD;
    }
    return ans;
}
void dfs(int x, int fa)
{
    int mx = 0;
    siz[x] = 1;
    for (register int i = head[x]; i; i = nxt[i])
    {
        if (ver[i] == fa)
            continue;
        dfs(ver[i], x);
        siz[x] += siz[ver[i]];
        mx = max(mx, siz[ver[i]]);
    }
    if (max(mx, n - siz[x]) <= n / 2)
        vet.push_back(x);
}
void efs(int x, int fa)
{
    siz[x] = 1;
    for (register int i = head[x]; i; i = nxt[i])
    {
        if (ver[i] == fa)
            continue;
        efs(ver[i], x);
        siz[x] += siz[ver[i]];
    }
}
inline long long cnm(int n, int m)
{
    if (n < m)
        return 0;
    long long cjr = jc[n];
    cjr *= jcny[m];
    cjr %= MOD;
    cjr *= jcny[n - m];
    return cjr % MOD;
}
inline long long anm(int n, int m)
{
    if (n < m)
        return 0;
    long long cjr = jc[n];
    cjr *= jcny[n - m];
    return cjr % MOD;
}
signed main()
{
#ifdef lky233
    freopen("testdata.in", "r", stdin);
    freopen("testdata.out", "w", stdout);
#endif
    n = poread<int>();
    for (register int i = 1; i < n; ++i)
    {
        int x, y;
        x = poread<int>();
        y = poread<int>();
        add(x, y);
        add(y, x);
    }
    dfs(1, 0);
    jc[0] = 1;
    for (register int i = 1; i <= n; ++i)
        jc[i] = (jc[i - 1] * i) % MOD;
    jcny[n] = power<long long>(jc[n], MOD - 2);
    for (register int i = n - 1; i >= 0; --i)
        jcny[i] = (jcny[i + 1] * (i + 1)) % MOD;
    if (vet.size() == 2)
    {
        cout << (jc[n / 2] * jc[n / 2]) % MOD << endl;
        return 0;
    }
    f[0] = 1;
    int rt = vet[0];
    efs(rt, 0);
    int ttt = 0;
    for (register int i = head[rt]; i; i = nxt[i])
    {
        ttt += siz[ver[i]];
        for (register int j = ttt; j >= 0; --j)
            for (register int k = 1; k <= min(j, siz[ver[i]]); ++k)
            {
                long long tmp = f[j - k];
                tmp *= cnm(siz[ver[i]], k);
                tmp %= MOD;
                tmp *= anm(siz[ver[i]], k);
                f[j] = (f[j] + tmp) % MOD;
            }
    }
    long long ans = 0;
    for (register int i = 0; i <= n; ++i)
        if (i & 1)
            ans -= f[i] * jc[n - i], ans %= MOD, ans += MOD, ans %= MOD;
        else
            ans = (ans + f[i] * jc[n - i]) % MOD;
    cout << ans << endl;
}

### 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 <bits/stdc++.h>
namespace fdata
{
inline char nextchar()
{
    static const int BS = 1 << 21;
    static char buf[BS], *st, *ed;
    if (st == ed)
        ed = buf + fread(st = buf, 1, BS, stdin);
    return st == ed ? -1 : *st++;
}
template <typename T>
inline T poread()
{
    T ret = 0;
    char ch;
    while (!isdigit(ch = nextchar()))
        ;

    do
        ret = ret * 10 + ch - '0';
    while (isdigit(ch = nextchar()));
    return ret;
}
} // namespace fdata
using namespace std;
using fdata::poread;
#define int long long
const int MAXN = 5e3 + 1;
const int MAXM = 1e7 + 1;
const int MOD = 1e9 + 7;
int n;
int ver[MAXM], nxt[MAXM], head[MAXN], tot;
int siz[MAXN];
long long jc[MAXN], jcny[MAXN];
long long f[MAXN];
vector<int> vet;
inline void add(int x, int y)
{
    ver[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
}
template <typename T>
inline T power(T a, int b)
{
    T ans = 1 % MOD;
    for (; b; b >>= 1)
    {
        if (b & 1)
            ans = (long long)ans * a % MOD;
        a = (long long)a * a % MOD;
    }
    return ans;
}
void dfs(int x, int fa)
{
    int mx = 0;
    siz[x] = 1;
    for (register int i = head[x]; i; i = nxt[i])
    {
        if (ver[i] == fa)
            continue;
        dfs(ver[i], x);
        siz[x] += siz[ver[i]];
        mx = max(mx, siz[ver[i]]);
    }
    if (max(mx, n - siz[x]) <= n / 2)
        vet.push_back(x);
}
void efs(int x, int fa)
{
    siz[x] = 1;
    for (register int i = head[x]; i; i = nxt[i])
    {
        if (ver[i] == fa)
            continue;
        efs(ver[i], x);
        siz[x] += siz[ver[i]];
    }
}
inline long long cnm(int n, int m)
{
    if (n < m)
        return 0;
    long long cjr = jc[n];
    cjr *= jcny[m];
    cjr %= MOD;
    cjr *= jcny[n - m];
    return cjr % MOD;
}
inline long long anm(int n, int m)
{
    if (n < m)
        return 0;
    long long cjr = jc[n];
    cjr *= jcny[n - m];
    return cjr % MOD;
}
signed main()
{
#ifdef lky233
    freopen("testdata.in", "r", stdin);
    freopen("testdata.out", "w", stdout);
#endif
    n = poread<int>();
    for (register int i = 1; i < n; ++i)
    {
        int x, y;
        x = poread<int>();
        y = poread<int>();
        add(x, y);
        add(y, x);
    }
    dfs(1, 0);
    jc[0] = 1;
    for (register int i = 1; i <= n; ++i)
        jc[i] = (jc[i - 1] * i) % MOD;
    jcny[n] = power<long long>(jc[n], MOD - 2);
    for (register int i = n - 1; i >= 0; --i)
        jcny[i] = (jcny[i + 1] * (i + 1)) % MOD;
    if (vet.size() == 2)
    {
        cout << (jc[n / 2] * jc[n / 2]) % MOD << endl;
        return 0;
    }
    f[0] = 1;
    int rt = vet[0];
    efs(rt, 0);
    int ttt = 0;
    for (register int i = head[rt]; i; i = nxt[i])
    {
        ttt += siz[ver[i]];
        for (register int j = ttt; j >= 0; --j)
            for (register int k = 1; k <= min(j, siz[ver[i]]); ++k)
            {
                long long tmp = f[j - k];
                tmp *= cnm(siz[ver[i]], k);
                tmp %= MOD;
                tmp *= anm(siz[ver[i]], k);
                f[j] = (f[j] + tmp) % MOD;
            }
    }
    long long ans = 0;
    for (register int i = 0; i <= n; ++i)
        if (i & 1)
            ans -= f[i] * jc[n - i], ans %= MOD, ans += MOD, ans %= MOD;
        else
            ans = (ans + f[i] * jc[n - i]) % MOD;
    cout << ans << endl;
}

```