#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

#define maxN 5011
#define mod 1000000007

int n, i, x, y;
int down[maxN];
vector<int> list[maxN], aux;

ll ans;
ll dp[maxN], loc[maxN], rez[maxN];

void compute_loc(int cnt) {
    int i, j;

    for (i = 0; i <= cnt; i++) loc[i] = 0;
    loc[0] = 1;

    for (i = 1; i <= cnt; i++) {
        for (j = i; j > 0; j--) {
            loc[j] += loc[j - 1] * (cnt - j + 1);
            loc[j] %= mod;
        }
    }
}

void solve() {
    int i, j, cnt;

    dp[0] = 1;
    for (auto v : aux) {
        cnt = v;

        compute_loc(cnt);
        for (i = 0; i <= n; i++) {
            rez[i] = dp[i];
            dp[i] = 0;
        }

        for (i = 0; i <= n; i++) {
            for (j = 0; j <= cnt && j <= i; j++) {
                dp[i] += rez[i - j] * loc[j];
                dp[i] %= mod;
            }
        }
    }

    for (i = 0; i <= n; i++) {
        for (j = 1; i + j <= n; j++)
            dp[i] = (dp[i] * j) % mod;

        if (i % 2 == 1) dp[i] = mod - dp[i];
        ans += dp[i];
    }

    ans %= mod;
    cout << ans;
}

void dfs(int node, int root) {
    bool ok = true;
    down[node] = 1;
    for (auto to : list[node]) {
        if (to == root) continue;
        dfs(to, node);
        down[node] += down[to];
        if (down[to] > n / 2) ok = false;
    }

    if (n - down[node] > n / 2) ok = false;

    if (ok) {
        if (down[node] * 2 == n) {
            ans = 1;
            for (i = 1; i <= down[node]; i++)
                ans = (ans * i) % mod;
            ans = (ans * ans) % mod;
            cout << ans;
            exit(0);
        } else {
            for (auto to : list[node])
                if (to != root)
                    aux.pb(down[to]);
            aux.pb(0);
            if (down[node] != n) aux.pb(n - down[node]);
            solve();
            exit(0);
        }
    }
}

int main()
{
  //  freopen("test.in","r",stdin);

    cin >> n;
    for (i = 1; i < n; i++) {
        cin >> x >> y;
        list[x].pb(y);
        list[y].pb(x);
    }

    dfs(1, 0);


    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 <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

#define maxN 5011
#define mod 1000000007

int n, i, x, y;
int down[maxN];
vector<int> list[maxN], aux;

ll ans;
ll dp[maxN], loc[maxN], rez[maxN];

void compute_loc(int cnt) {
    int i, j;

    for (i = 0; i <= cnt; i++) loc[i] = 0;
    loc[0] = 1;

    for (i = 1; i <= cnt; i++) {
        for (j = i; j > 0; j--) {
            loc[j] += loc[j - 1] * (cnt - j + 1);
            loc[j] %= mod;
        }
    }
}

void solve() {
    int i, j, cnt;

    dp[0] = 1;
    for (auto v : aux) {
        cnt = v;

        compute_loc(cnt);
        for (i = 0; i <= n; i++) {
            rez[i] = dp[i];
            dp[i] = 0;
        }

        for (i = 0; i <= n; i++) {
            for (j = 0; j <= cnt && j <= i; j++) {
                dp[i] += rez[i - j] * loc[j];
                dp[i] %= mod;
            }
        }
    }

    for (i = 0; i <= n; i++) {
        for (j = 1; i + j <= n; j++)
            dp[i] = (dp[i] * j) % mod;

        if (i % 2 == 1) dp[i] = mod - dp[i];
        ans += dp[i];
    }

    ans %= mod;
    cout << ans;
}

void dfs(int node, int root) {
    bool ok = true;
    down[node] = 1;
    for (auto to : list[node]) {
        if (to == root) continue;
        dfs(to, node);
        down[node] += down[to];
        if (down[to] > n / 2) ok = false;
    }

    if (n - down[node] > n / 2) ok = false;

    if (ok) {
        if (down[node] * 2 == n) {
            ans = 1;
            for (i = 1; i <= down[node]; i++)
                ans = (ans * i) % mod;
            ans = (ans * ans) % mod;
            cout << ans;
            exit(0);
        } else {
            for (auto to : list[node])
                if (to != root)
                    aux.pb(down[to]);
            aux.pb(0);
            if (down[node] != n) aux.pb(n - down[node]);
            solve();
            exit(0);
        }
    }
}

int main()
{
  //  freopen("test.in","r",stdin);

    cin >> n;
    for (i = 1; i < n; i++) {
        cin >> x >> y;
        list[x].pb(y);
        list[y].pb(x);
    }

    dfs(1, 0);


    return 0;
}

```