//https://arc087.contest.atcoder.jp/tasks/arc087_d

#include<bits/stdc++.h>
const int N = 5005;
const int mod = 1e9 + 7;
using namespace std;

vector <int> adj[N];
vector <int> mv;
int n, C[N][N], f[N], a[N], d[N], cnt, cen;
int dp[N][N], ans;

void add(int&a, int b){
    a += b; if (a >= mod) a -= mod; if (a < 0) a += mod;
}

void dfs(int u, int p){
    d[u] = 1; int ck = 0;
    for (auto v : adj[u]){
        if (v == p) continue;
        dfs(v, u);
        d[u] += d[v];
        if (d[v] > n/2) ck = true;
    }
    if (n-d[u] > n/2) ck = true;
    if (!ck) mv.push_back(u);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    for (int i = 0; i < N; i++) f[i] = ((i) ? 1LL * f[i-1] * i % mod : 1);
    for (int i = 0; i < N; i++) for (int j = 0; j <= i; j++){
        C[i][j] = ((j == 0) ? 1 : (C[i-1][j] + C[i-1][j-1]) % mod);
    }
    cin >> n;
    for (int i = 2; i <= n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 1);
    if (mv.size() == 2){
        a[++cnt] = n/2; a[++cnt] = n/2;
    }
    else{
        cen = mv[0];
        dfs(cen, cen);
        for (auto v : adj[cen]) a[++cnt] = d[v];
    }
    dp[0][0] = 1;
    for (int i = 1; i <= cnt; i++){
        for (int sum = 0; sum <= n; sum++){
            for (int k = 0; k <= a[i]; k++){
                if (sum >= k) add(dp[i][sum], 1LL * dp[i-1][sum-k] * C[a[i]][k] % mod * C[a[i]][k] % mod * f[k] % mod);
            }
        }
    }
    for (int i = 0; i <= n; i++){
        if (i&1) add(ans, -1LL * dp[cnt][i] * f[n-i] % mod);
        else add(ans, 1LL * dp[cnt][i] * f[n-i] % mod);
    }
    cout << ans;
}

### Prompt

Please create a solution in CPP 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
//https://arc087.contest.atcoder.jp/tasks/arc087_d

#include<bits/stdc++.h>
const int N = 5005;
const int mod = 1e9 + 7;
using namespace std;

vector <int> adj[N];
vector <int> mv;
int n, C[N][N], f[N], a[N], d[N], cnt, cen;
int dp[N][N], ans;

void add(int&a, int b){
    a += b; if (a >= mod) a -= mod; if (a < 0) a += mod;
}

void dfs(int u, int p){
    d[u] = 1; int ck = 0;
    for (auto v : adj[u]){
        if (v == p) continue;
        dfs(v, u);
        d[u] += d[v];
        if (d[v] > n/2) ck = true;
    }
    if (n-d[u] > n/2) ck = true;
    if (!ck) mv.push_back(u);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    for (int i = 0; i < N; i++) f[i] = ((i) ? 1LL * f[i-1] * i % mod : 1);
    for (int i = 0; i < N; i++) for (int j = 0; j <= i; j++){
        C[i][j] = ((j == 0) ? 1 : (C[i-1][j] + C[i-1][j-1]) % mod);
    }
    cin >> n;
    for (int i = 2; i <= n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 1);
    if (mv.size() == 2){
        a[++cnt] = n/2; a[++cnt] = n/2;
    }
    else{
        cen = mv[0];
        dfs(cen, cen);
        for (auto v : adj[cen]) a[++cnt] = d[v];
    }
    dp[0][0] = 1;
    for (int i = 1; i <= cnt; i++){
        for (int sum = 0; sum <= n; sum++){
            for (int k = 0; k <= a[i]; k++){
                if (sum >= k) add(dp[i][sum], 1LL * dp[i-1][sum-k] * C[a[i]][k] % mod * C[a[i]][k] % mod * f[k] % mod);
            }
        }
    }
    for (int i = 0; i <= n; i++){
        if (i&1) add(ans, -1LL * dp[cnt][i] * f[n-i] % mod);
        else add(ans, 1LL * dp[cnt][i] * f[n-i] % mod);
    }
    cout << ans;
}

```