#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
const int mod = (int)1e9 + 7;
int sum(int a, int b) {
    int s = a + b;
    if (s >= mod) s -= mod;
    return s;
}
int mult(int a, int b) {
    return (1LL * a * b) % mod;
}
int pw(int a, int b) {
    if (b == 0) return 1;
    if (b & 1) return mult(a, pw(a, b - 1));
    int res = pw(a, b / 2);
    return mult(res, res);
}
const int maxN = 5005;
int fact[maxN];
int invfact[maxN];
int inv[maxN];
void init() {
    fact[0] = invfact[0] = inv[1] = fact[1] = invfact[1] = 1;
    for (int i = 2; i < maxN; i++) {
        fact[i] = mult(fact[i - 1], i);
        inv[i] = mult(mod - mod / i, inv[mod % i]);
        invfact[i] = mult(invfact[i - 1], inv[i]);
    }
}
int cnk(int n, int k) {
    if (n < k || k < 0) return 0;
    return mult(fact[n], mult(invfact[k], invfact[n - k]));
}
vector < int > g[maxN];
int n;
int sz[maxN];
int sb[maxN];
void dfs(int v, int p) {
    sz[v] = 1;
    sb[v] = 0;
    for (int to : g[v]) {
        if (to == p) continue;
        dfs(to, v);
        sz[v] += sz[to];
        sb[v] = max(sb[v], sz[to]);
    }
}
int dp[maxN][maxN];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("input.txt", "r", stdin);
    init();
    cin >> n;
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        g[x].emplace_back(y);
        g[y].emplace_back(x);
    }
    dfs(1, -1);
    int c = -1;
    for (int i = 1; i <= n; i++) {
        if (sb[i] <= n / 2 && n - sz[i] <= n / 2) {
            c = i;
            break;
        }
    }
    assert(c != -1);
    dfs(c, -1);
    vector < int > sizes;
    for (int to : g[c]) {
        sizes.emplace_back(sz[to]);
    }
    dp[0][0] = 1;
    int p = 0;
    for (int i = 0; i < sizes.size(); i++) {
        vector < int > f(sizes[i] + 1);
        for (int j = 0; j <= sizes[i]; j++) {
            f[j] = mult(fact[j], mult(cnk(sizes[i], j), cnk(sizes[i], j)));
            if (j & 1) f[j] = (mod - f[j]) % mod;
        }
        for (int at = 0; at <= p; at++) {
            for (int j = 0; j <= sizes[i]; j++) {
                dp[i + 1][at + j] = sum(dp[i + 1][at + j], mult(dp[i][at], f[j]));
            }
        }
        p += sizes[i];
    }
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        ans = sum(ans, mult(dp[sizes.size()][i], fact[n - i]));
    }
    cout << 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
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
const int mod = (int)1e9 + 7;
int sum(int a, int b) {
    int s = a + b;
    if (s >= mod) s -= mod;
    return s;
}
int mult(int a, int b) {
    return (1LL * a * b) % mod;
}
int pw(int a, int b) {
    if (b == 0) return 1;
    if (b & 1) return mult(a, pw(a, b - 1));
    int res = pw(a, b / 2);
    return mult(res, res);
}
const int maxN = 5005;
int fact[maxN];
int invfact[maxN];
int inv[maxN];
void init() {
    fact[0] = invfact[0] = inv[1] = fact[1] = invfact[1] = 1;
    for (int i = 2; i < maxN; i++) {
        fact[i] = mult(fact[i - 1], i);
        inv[i] = mult(mod - mod / i, inv[mod % i]);
        invfact[i] = mult(invfact[i - 1], inv[i]);
    }
}
int cnk(int n, int k) {
    if (n < k || k < 0) return 0;
    return mult(fact[n], mult(invfact[k], invfact[n - k]));
}
vector < int > g[maxN];
int n;
int sz[maxN];
int sb[maxN];
void dfs(int v, int p) {
    sz[v] = 1;
    sb[v] = 0;
    for (int to : g[v]) {
        if (to == p) continue;
        dfs(to, v);
        sz[v] += sz[to];
        sb[v] = max(sb[v], sz[to]);
    }
}
int dp[maxN][maxN];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("input.txt", "r", stdin);
    init();
    cin >> n;
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        g[x].emplace_back(y);
        g[y].emplace_back(x);
    }
    dfs(1, -1);
    int c = -1;
    for (int i = 1; i <= n; i++) {
        if (sb[i] <= n / 2 && n - sz[i] <= n / 2) {
            c = i;
            break;
        }
    }
    assert(c != -1);
    dfs(c, -1);
    vector < int > sizes;
    for (int to : g[c]) {
        sizes.emplace_back(sz[to]);
    }
    dp[0][0] = 1;
    int p = 0;
    for (int i = 0; i < sizes.size(); i++) {
        vector < int > f(sizes[i] + 1);
        for (int j = 0; j <= sizes[i]; j++) {
            f[j] = mult(fact[j], mult(cnk(sizes[i], j), cnk(sizes[i], j)));
            if (j & 1) f[j] = (mod - f[j]) % mod;
        }
        for (int at = 0; at <= p; at++) {
            for (int j = 0; j <= sizes[i]; j++) {
                dp[i + 1][at + j] = sum(dp[i + 1][at + j], mult(dp[i][at], f[j]));
            }
        }
        p += sizes[i];
    }
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        ans = sum(ans, mult(dp[sizes.size()][i], fact[n - i]));
    }
    cout << ans;
    return 0;
}
```