#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define forn(i, a, n) for (int i = (int)(a); i < (int)(n); ++i)
#define ford(i, a, n) for (int i = (int)(n) - 1; i >= (int)(a); --i)
#define fore(i, a, n) for (int i = (int)(a); i <= (int)(n); ++i)
#define all(a) (a).begin(), (a).end()
#define fs first
#define sn second
#define trace(a)\
    for (auto i : a) cerr << i << ' ';\
    cerr << '\n'
#define eb emplace_back

#ifndef M_PI
const ld M_PI = acos(-1.0);
#endif

template<typename T>
inline void setmax(T& a, T b) {
    if (a < b) a = b;
}

template<typename T>
inline void setmin(T& a, T b) {
    if (a > b) a = b;
}

const ld eps = 1e-9;
const int INF = 2000000000;
const ll LINF = 1ll * INF * INF;
const ll MOD = 1000000007;

const int N = 5555;
vector<int> e[N];
int sz[N];
int n;

int find_sz(int u, int p) {
    sz[u] = 1;
    for (int v : e[u]) {
        if (v == p) continue;
        sz[u] += find_sz(v, u);
    }
    return sz[u];
}

pair<int, int> find_centroid(int u, int p) {
    int best = -1;
    for (int v : e[u]) {
        if (v == p) continue;
        if (best == -1 || sz[v] > sz[best])
            best = v;
    }
    if (best == -1 || 2 * sz[best] <= n)
        return {u, p};
    return find_centroid(best, u);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); 
    srand((unsigned)chrono::high_resolution_clock::now().time_since_epoch().count());
    cin >> n;
    forn(i, 1, n) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        e[u].eb(v);
        e[v].eb(u);
    }
    find_sz(0, -1);
    pair<int, int> c = find_centroid(0, -1);
    vector<int> sizes;
    int sum = 0;
    for (int u : e[c.fs]) {
        if (u == c.sn) continue;
        sizes.eb(sz[u]);
        sum += sz[u];
    }
    if (c.sn != -1) sizes.eb(n - 1 - sum);
    //trace(sizes);
    vector<ll> fact(n + 1);
    fact[0] = 1;
    fore(i, 1, n) fact[i] = fact[i - 1] * i % MOD;
    vector<vector<ll>> binom(n + 1, vector<ll>(n + 1));
    fore(i, 0, n) fore(j, 0, n) {
        if (j == 0) {
            binom[i][j] = 1;
            continue;
        }
        if (i == 0) {
            binom[i][j] = 0;
            continue;
        }
        binom[i][j] = binom[i - 1][j] + binom[i - 1][j - 1];
        if (binom[i][j] >= MOD) binom[i][j] -= MOD;
    }
    vector<ll> part(n + 1);
    part[0] = 1;
    for (int x : sizes) {
        vector<ll> npart(n + 1);
        fore(i, 0, n)
            fore(j, 0, x) {
                if (i + j > n) break;
                npart[i + j] += part[i] * binom[x][j] % MOD * binom[x][j] % MOD * fact[j];
                npart[i + j] %= MOD;
            }
        part = npart;
    }
    ll ans = 0;
    fore(i, 0, n) {
        ans += (n % 2 == i % 2 ? 1 : -1) * fact[i] * part[n - i];
        //cerr << i << ' ' << fact[i] << ' ' << part[n - i] << '\n';
        ans %= MOD;
    }
    if (ans < 0) ans += MOD;
    cout << ans << '\n';
}

### 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>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define forn(i, a, n) for (int i = (int)(a); i < (int)(n); ++i)
#define ford(i, a, n) for (int i = (int)(n) - 1; i >= (int)(a); --i)
#define fore(i, a, n) for (int i = (int)(a); i <= (int)(n); ++i)
#define all(a) (a).begin(), (a).end()
#define fs first
#define sn second
#define trace(a)\
    for (auto i : a) cerr << i << ' ';\
    cerr << '\n'
#define eb emplace_back

#ifndef M_PI
const ld M_PI = acos(-1.0);
#endif

template<typename T>
inline void setmax(T& a, T b) {
    if (a < b) a = b;
}

template<typename T>
inline void setmin(T& a, T b) {
    if (a > b) a = b;
}

const ld eps = 1e-9;
const int INF = 2000000000;
const ll LINF = 1ll * INF * INF;
const ll MOD = 1000000007;

const int N = 5555;
vector<int> e[N];
int sz[N];
int n;

int find_sz(int u, int p) {
    sz[u] = 1;
    for (int v : e[u]) {
        if (v == p) continue;
        sz[u] += find_sz(v, u);
    }
    return sz[u];
}

pair<int, int> find_centroid(int u, int p) {
    int best = -1;
    for (int v : e[u]) {
        if (v == p) continue;
        if (best == -1 || sz[v] > sz[best])
            best = v;
    }
    if (best == -1 || 2 * sz[best] <= n)
        return {u, p};
    return find_centroid(best, u);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); 
    srand((unsigned)chrono::high_resolution_clock::now().time_since_epoch().count());
    cin >> n;
    forn(i, 1, n) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        e[u].eb(v);
        e[v].eb(u);
    }
    find_sz(0, -1);
    pair<int, int> c = find_centroid(0, -1);
    vector<int> sizes;
    int sum = 0;
    for (int u : e[c.fs]) {
        if (u == c.sn) continue;
        sizes.eb(sz[u]);
        sum += sz[u];
    }
    if (c.sn != -1) sizes.eb(n - 1 - sum);
    //trace(sizes);
    vector<ll> fact(n + 1);
    fact[0] = 1;
    fore(i, 1, n) fact[i] = fact[i - 1] * i % MOD;
    vector<vector<ll>> binom(n + 1, vector<ll>(n + 1));
    fore(i, 0, n) fore(j, 0, n) {
        if (j == 0) {
            binom[i][j] = 1;
            continue;
        }
        if (i == 0) {
            binom[i][j] = 0;
            continue;
        }
        binom[i][j] = binom[i - 1][j] + binom[i - 1][j - 1];
        if (binom[i][j] >= MOD) binom[i][j] -= MOD;
    }
    vector<ll> part(n + 1);
    part[0] = 1;
    for (int x : sizes) {
        vector<ll> npart(n + 1);
        fore(i, 0, n)
            fore(j, 0, x) {
                if (i + j > n) break;
                npart[i + j] += part[i] * binom[x][j] % MOD * binom[x][j] % MOD * fact[j];
                npart[i + j] %= MOD;
            }
        part = npart;
    }
    ll ans = 0;
    fore(i, 0, n) {
        ans += (n % 2 == i % 2 ? 1 : -1) * fact[i] * part[n - i];
        //cerr << i << ' ' << fact[i] << ' ' << part[n - i] << '\n';
        ans %= MOD;
    }
    if (ans < 0) ans += MOD;
    cout << ans << '\n';
}

```