#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int mod = 1000*1000*1000+7;

int po(int x, int n) {
    int ret = 1;
    while(n) {
        if(n & 1) ret = 1LL * ret * x % mod;
        x = 1LL * x * x % mod;
        n >>= 1;
    }
    return ret;
}
int inv(int x) { return po(x, mod - 2); }
int fact[5010], invf[5010];
int comb(int n, int k) {
    return 1LL * fact[n] * invf[k] % mod * invf[n - k] % mod;
}

int N;
vector<vector<int> > adj;
vector<int> sz;

void dfs(int u, int p) {
    sz[u] = 1;
    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if(v == p) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

int dfs2(int u, int p) {
    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if(v == p) continue;
        if(sz[v] > sz[0] / 2) return dfs2(v, u);
    }
    return u;
}

vector<int> tmp;
int ans = 0;

vector<vector<int> > cc;
int dp(int g, int k) {
    if(g == tmp.size()) return k == 0;
    int &ret = cc[g][k];
    if(ret != -1) return ret;

    ret = 0;
    for(int i = 0; i <= min(k, tmp[g]); i++) {
        ret += 1LL * comb(tmp[g], i) * comb(tmp[g], i) % mod * fact[i] % mod * dp(g + 1, k - i) % mod;
        ret %= mod;
    }
    return ret;
}

void solve() {
    int sum = 0;
    for(int i = 0; i < tmp.size(); i++) {
        sum += tmp[i];
    }

    cc = vector<vector<int> >(tmp.size(), vector<int>(sum + 1, -1));

    for(int i = 0; i <= sum; i++) {
        ans += 1LL * dp(0, i) * fact[sum - i] % mod * (i % 2? -1 : 1);
        ans = (ans % mod + mod) % mod;
    }
}

int main() {
    fact[0] = 1;
    for(int i = 1; i < 5010; i++) {
        fact[i] = 1LL * fact[i - 1] * i % mod;
    }
    for(int i = 0; i < 5010; i++) {
        invf[i] = inv(fact[i]);
    }

    scanf("%d", &N);

    adj.resize(N);
    for(int i = 0; i < N - 1; i++) {
        int u, v; scanf("%d %d", &u, &v);
        u--; v--;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    sz.resize(N);
    dfs(0, -1);

    int C = dfs2(0, -1);

    for(int i = 0; i < adj[C].size(); i++) {
        int v = adj[C][i];
        if(N % 2 == 0 && sz[v] == N / 2) {
            printf("%d", 1LL * fact[N / 2] * fact[N / 2] % mod);
            return 0;
        }
    }

    dfs(C, -1);

    for(int i = 0; i < adj[C].size(); i++) {
        int v = adj[C][i];

        tmp.push_back(sz[v]);
    }
    solve();

    tmp.push_back(1);
    solve();

    printf("%d", ans);
}

### 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>
using namespace std;

typedef pair<int, int> pii;

const int mod = 1000*1000*1000+7;

int po(int x, int n) {
    int ret = 1;
    while(n) {
        if(n & 1) ret = 1LL * ret * x % mod;
        x = 1LL * x * x % mod;
        n >>= 1;
    }
    return ret;
}
int inv(int x) { return po(x, mod - 2); }
int fact[5010], invf[5010];
int comb(int n, int k) {
    return 1LL * fact[n] * invf[k] % mod * invf[n - k] % mod;
}

int N;
vector<vector<int> > adj;
vector<int> sz;

void dfs(int u, int p) {
    sz[u] = 1;
    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if(v == p) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

int dfs2(int u, int p) {
    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if(v == p) continue;
        if(sz[v] > sz[0] / 2) return dfs2(v, u);
    }
    return u;
}

vector<int> tmp;
int ans = 0;

vector<vector<int> > cc;
int dp(int g, int k) {
    if(g == tmp.size()) return k == 0;
    int &ret = cc[g][k];
    if(ret != -1) return ret;

    ret = 0;
    for(int i = 0; i <= min(k, tmp[g]); i++) {
        ret += 1LL * comb(tmp[g], i) * comb(tmp[g], i) % mod * fact[i] % mod * dp(g + 1, k - i) % mod;
        ret %= mod;
    }
    return ret;
}

void solve() {
    int sum = 0;
    for(int i = 0; i < tmp.size(); i++) {
        sum += tmp[i];
    }

    cc = vector<vector<int> >(tmp.size(), vector<int>(sum + 1, -1));

    for(int i = 0; i <= sum; i++) {
        ans += 1LL * dp(0, i) * fact[sum - i] % mod * (i % 2? -1 : 1);
        ans = (ans % mod + mod) % mod;
    }
}

int main() {
    fact[0] = 1;
    for(int i = 1; i < 5010; i++) {
        fact[i] = 1LL * fact[i - 1] * i % mod;
    }
    for(int i = 0; i < 5010; i++) {
        invf[i] = inv(fact[i]);
    }

    scanf("%d", &N);

    adj.resize(N);
    for(int i = 0; i < N - 1; i++) {
        int u, v; scanf("%d %d", &u, &v);
        u--; v--;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    sz.resize(N);
    dfs(0, -1);

    int C = dfs2(0, -1);

    for(int i = 0; i < adj[C].size(); i++) {
        int v = adj[C][i];
        if(N % 2 == 0 && sz[v] == N / 2) {
            printf("%d", 1LL * fact[N / 2] * fact[N / 2] % mod);
            return 0;
        }
    }

    dfs(C, -1);

    for(int i = 0; i < adj[C].size(); i++) {
        int v = adj[C][i];

        tmp.push_back(sz[v]);
    }
    solve();

    tmp.push_back(1);
    solve();

    printf("%d", ans);
}

```