#include <bits/stdc++.h>
using i64 = long long;

constexpr i64 mod = 1000000007;
std::vector<std::deque<int>> g;
long long *fact, *inv;

template <class T>
T pow(T x, T n, T mod) {
    T ret = 1;
    while(n > 0) {
        if ((n & 1) == 1) ret = (ret * x) % mod;
        x = (x * x) % mod;
        n >>= 1;
    }
    return ret;
}

template <class T>
T inverse(T x, T p) { return pow(x, p - 2, p); }

void init_factorial(int n, long long mod) {
    fact = new long long[n + 1];
    inv = new long long[n + 1];
    fact[0] = 1;
    for (long long i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % mod;
    inv[n] = inverse(fact[n], mod);
    for (long long i = n; i > 0; i--) inv[i - 1] = inv[i] * i % mod;
}

int n;
std::vector<int> centroids, ch;
void dfs(int v, int p) {
    ch[v] = 1;
    bool flg = true;
    for (auto to : g[v]) {
        if (to == p) continue;
        dfs(to, v);
        ch[v] += ch[to];
        if (ch[to] > n / 2) flg = false;
    }
    if (flg && n - ch[v] <= n / 2) centroids.push_back(v);
}

int dfs2(int v, int p) {
    ch[v] = 1;
    for (auto to : g[v]) {
        if (to == p) continue;
        ch[v] += dfs2(to, v);
    }
    return ch[v];
}

int main() {
    std::cin >> n;
    g.resize(n); ch.resize(n);
    init_factorial(n, mod);
    for (int i = 1; i < n; i++) {
        int x, y;
        std::cin >> x >> y;
        --x; --y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    dfs(0, -1);

    if (centroids.size() == 2) {
        std::cout << fact[n / 2] * fact[n / 2] % mod << std::endl;
        return 0;
    }

    int c = centroids.front();
    int m = g[c].size();

    dfs2(c, -1);

    std::vector<std::vector<i64>> dp(m + 1, std::vector<i64>(n));
    dp[0][0] = 1;
    int max = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 0, tot = ch[g[c][i - 1]]; j <= tot; j++) {
            for (int k = 0; k <= max; k++) {
                dp[i][j + k] = (dp[i][j + k] + dp[i - 1][k] * fact[tot] % mod * fact[tot] % mod * inv[j] % mod * inv[j] % mod * inv[tot - j] % mod * inv[tot - j] % mod * fact[j] % mod) % mod;
            }
        }
        max += ch[g[c][i - 1]];
    }

    i64 ret = 0;
    for (int i = 0; i < n; i++) {
        ret = (ret + (mod + (i % 2 ? -1 : 1) * fact[n - i]) % mod * dp[m][i] % mod) % mod;
    }
    std::cout << ret << std::endl;

    return 0;
}

### Prompt

Create a solution in Cpp for 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 i64 = long long;

constexpr i64 mod = 1000000007;
std::vector<std::deque<int>> g;
long long *fact, *inv;

template <class T>
T pow(T x, T n, T mod) {
    T ret = 1;
    while(n > 0) {
        if ((n & 1) == 1) ret = (ret * x) % mod;
        x = (x * x) % mod;
        n >>= 1;
    }
    return ret;
}

template <class T>
T inverse(T x, T p) { return pow(x, p - 2, p); }

void init_factorial(int n, long long mod) {
    fact = new long long[n + 1];
    inv = new long long[n + 1];
    fact[0] = 1;
    for (long long i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % mod;
    inv[n] = inverse(fact[n], mod);
    for (long long i = n; i > 0; i--) inv[i - 1] = inv[i] * i % mod;
}

int n;
std::vector<int> centroids, ch;
void dfs(int v, int p) {
    ch[v] = 1;
    bool flg = true;
    for (auto to : g[v]) {
        if (to == p) continue;
        dfs(to, v);
        ch[v] += ch[to];
        if (ch[to] > n / 2) flg = false;
    }
    if (flg && n - ch[v] <= n / 2) centroids.push_back(v);
}

int dfs2(int v, int p) {
    ch[v] = 1;
    for (auto to : g[v]) {
        if (to == p) continue;
        ch[v] += dfs2(to, v);
    }
    return ch[v];
}

int main() {
    std::cin >> n;
    g.resize(n); ch.resize(n);
    init_factorial(n, mod);
    for (int i = 1; i < n; i++) {
        int x, y;
        std::cin >> x >> y;
        --x; --y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    dfs(0, -1);

    if (centroids.size() == 2) {
        std::cout << fact[n / 2] * fact[n / 2] % mod << std::endl;
        return 0;
    }

    int c = centroids.front();
    int m = g[c].size();

    dfs2(c, -1);

    std::vector<std::vector<i64>> dp(m + 1, std::vector<i64>(n));
    dp[0][0] = 1;
    int max = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 0, tot = ch[g[c][i - 1]]; j <= tot; j++) {
            for (int k = 0; k <= max; k++) {
                dp[i][j + k] = (dp[i][j + k] + dp[i - 1][k] * fact[tot] % mod * fact[tot] % mod * inv[j] % mod * inv[j] % mod * inv[tot - j] % mod * inv[tot - j] % mod * fact[j] % mod) % mod;
            }
        }
        max += ch[g[c][i - 1]];
    }

    i64 ret = 0;
    for (int i = 0; i < n; i++) {
        ret = (ret + (mod + (i % 2 ? -1 : 1) * fact[n - i]) % mod * dp[m][i] % mod) % mod;
    }
    std::cout << ret << std::endl;

    return 0;
}

```