#include<bits/stdc++.h>

using namespace std;

#define pb push_back

const int N = 5e3 + 5, mod = 1e9 + 7;
int n, child[N], cen[2], pterCen, fact[N], invFact[N], a[N], pterA, g[N], pterG;
vector<int> gr[N];

int binpow (int aa, int mm) {
    int ret = 1;
    for (; mm; mm >>= 1, aa = (1LL * aa * aa) % mod) if (mm & 1) ret = (1LL * ret * aa) % mod;
    return ret;
}

void dfs (int u, int p) {
    child[u] = 1;
    bool isCentroid = 1;
    for (int v : gr[u]) if (v != p) {
        dfs(v, u);
        child[u] += child[v];
        if (child[v] > n / 2) isCentroid = 0;
    }
    if (n - child[u] > n / 2) isCentroid = 0;
    if (isCentroid) cen[pterCen ++] = u;
}

int C (int kk, int nn) { return (1LL * (1LL * fact[nn] * invFact[kk]) % mod * invFact[nn - kk]) % mod; }

int main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    fact[0] = 1;
    for (int i = 1; i < N; ++i) fact[i] = (1LL * fact[i - 1] * i) % mod;
    for (int i = 0; i < N; ++i) invFact[i] = binpow(fact[i], mod - 2) % mod;
    cin >> n;
    for (int _ = 1; _ < n; ++_) {
        int u, v; cin >> u >> v;
        gr[u].pb(v); gr[v].pb(u);
    }

    dfs(1, 1);

    if (pterCen == 2) return cout << (1LL * fact[n / 2] * fact[n / 2]) % mod, 0;

    dfs(cen[0], cen[0]);
    for (int u : gr[cen[0] ]) a[++pterA] = child[u];

    g[pterG] = 1;

    for (int i = 1; i <= pterA; ++i) {
        for (int j = pterG; j >= 0; --j) {
            for (int k = 1; k <= a[i]; ++k) {
                g[j + k] = (g[j + k] + (1LL * (1LL * (1LL * g[j] * C(k, a[i]) ) % mod * C(k, a[i]) ) % mod * fact[k]) ) % mod;
            }
        }
        pterG += a[i];
    }

    int ans = 0;
    for (int i = 0; i < n; ++i) {
//        cout << g[i] << '\n';
        if (i & 1) ans = (ans - 1LL * g[i] * fact[n - i]) % mod;
        else ans = (ans + 1LL * g[i] * fact[n - i]) % mod;
    }

    cout << (ans + mod) % mod;

    return 0;
}

### Prompt

Generate 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>

using namespace std;

#define pb push_back

const int N = 5e3 + 5, mod = 1e9 + 7;
int n, child[N], cen[2], pterCen, fact[N], invFact[N], a[N], pterA, g[N], pterG;
vector<int> gr[N];

int binpow (int aa, int mm) {
    int ret = 1;
    for (; mm; mm >>= 1, aa = (1LL * aa * aa) % mod) if (mm & 1) ret = (1LL * ret * aa) % mod;
    return ret;
}

void dfs (int u, int p) {
    child[u] = 1;
    bool isCentroid = 1;
    for (int v : gr[u]) if (v != p) {
        dfs(v, u);
        child[u] += child[v];
        if (child[v] > n / 2) isCentroid = 0;
    }
    if (n - child[u] > n / 2) isCentroid = 0;
    if (isCentroid) cen[pterCen ++] = u;
}

int C (int kk, int nn) { return (1LL * (1LL * fact[nn] * invFact[kk]) % mod * invFact[nn - kk]) % mod; }

int main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    fact[0] = 1;
    for (int i = 1; i < N; ++i) fact[i] = (1LL * fact[i - 1] * i) % mod;
    for (int i = 0; i < N; ++i) invFact[i] = binpow(fact[i], mod - 2) % mod;
    cin >> n;
    for (int _ = 1; _ < n; ++_) {
        int u, v; cin >> u >> v;
        gr[u].pb(v); gr[v].pb(u);
    }

    dfs(1, 1);

    if (pterCen == 2) return cout << (1LL * fact[n / 2] * fact[n / 2]) % mod, 0;

    dfs(cen[0], cen[0]);
    for (int u : gr[cen[0] ]) a[++pterA] = child[u];

    g[pterG] = 1;

    for (int i = 1; i <= pterA; ++i) {
        for (int j = pterG; j >= 0; --j) {
            for (int k = 1; k <= a[i]; ++k) {
                g[j + k] = (g[j + k] + (1LL * (1LL * (1LL * g[j] * C(k, a[i]) ) % mod * C(k, a[i]) ) % mod * fact[k]) ) % mod;
            }
        }
        pterG += a[i];
    }

    int ans = 0;
    for (int i = 0; i < n; ++i) {
//        cout << g[i] << '\n';
        if (i & 1) ans = (ans - 1LL * g[i] * fact[n - i]) % mod;
        else ans = (ans + 1LL * g[i] * fact[n - i]) % mod;
    }

    cout << (ans + mod) % mod;

    return 0;
}

```