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

#define forn(i,n) for(int i=0;i<(int)(n);i++)
#define si(c) ((int)(c).size())
#define forsn(i,s,n) for(int i = (int)(s); i<((int)n); i++)
#define dforsn(i,s,n) for(int i = (int)(n)-1; i>=((int)s); i--)
#define all(c) (c).begin(), (c).end()
#define D(a) cerr << #a << "=" << (a) << endl;
#define pb push_back
#define eb emplace_back
#define mp make_pair

typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pii;

const int N = 5050;
const int MOD = 1e9 + 7;

int n, comb[N][N], fact[N];
vi adj[N];

int sz[N], pref[N];
void dfs(int u, int p) {
    sz[u] = 1;
    pref[u] = -1;
    for (int v : adj[u]) if (v != p) {
        dfs(v,u);
        sz[u] += sz[v];
        if (pref[u] == -1 || (sz[v] > sz[pref[u]])) pref[u] = v;
    }
}

int dp[N][N];

void add(int &x, int y) { 
    x += y;
    if (x >= MOD) x -= MOD;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n;
    forn(_,n-1) {
        int u,v; cin >> u >> v;
        u--; v--;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    for (int x = 0; x <= n; x++) {
        comb[x][0] = 1;
        for (int y = 1; y <= x; y++) {
            comb[x][y] = comb[x-1][y-1] + comb[x-1][y];
            if (comb[x][y] >= MOD) comb[x][y] -= MOD;
        }
    }
    fact[0] = 1; for (int x = 1; x <= n; x++) fact[x] = ll(x) * fact[x-1] % MOD;

    dfs(0,-1);
    int c = 0;
    while (pref[c] != -1 && sz[pref[c]]*2 > n) c = pref[c];

    int sz = 1, ind = 1; dp[0][0] = 1;
    for (int v : adj[c]) {
        dfs(v,c);
        int n = ::sz[v];
        forn(k,n+1) {
            ll coef = (ll) fact[k] * comb[n][k] % MOD * comb[n][k] % MOD;
            forn(j,sz) add(dp[ind][j+k], (ll) dp[ind-1][j] * coef % MOD);
        }
        sz += n;
        ind++;
    }
    //forn(i,sz) cerr << dp[ind-1][i] << ' '; cerr << endl;

    ll ans = 0;
    forn(k,sz) {
        auto val = (ll) dp[ind-1][k] * fact[n-k] % MOD;
        if (k&1) ans -= val; else ans += val;
    }
    ans %= MOD; if (ans < 0) ans += MOD;
    cout << ans << endl;

    return 0;
}

### Prompt

Please formulate 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;

#define forn(i,n) for(int i=0;i<(int)(n);i++)
#define si(c) ((int)(c).size())
#define forsn(i,s,n) for(int i = (int)(s); i<((int)n); i++)
#define dforsn(i,s,n) for(int i = (int)(n)-1; i>=((int)s); i--)
#define all(c) (c).begin(), (c).end()
#define D(a) cerr << #a << "=" << (a) << endl;
#define pb push_back
#define eb emplace_back
#define mp make_pair

typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pii;

const int N = 5050;
const int MOD = 1e9 + 7;

int n, comb[N][N], fact[N];
vi adj[N];

int sz[N], pref[N];
void dfs(int u, int p) {
    sz[u] = 1;
    pref[u] = -1;
    for (int v : adj[u]) if (v != p) {
        dfs(v,u);
        sz[u] += sz[v];
        if (pref[u] == -1 || (sz[v] > sz[pref[u]])) pref[u] = v;
    }
}

int dp[N][N];

void add(int &x, int y) { 
    x += y;
    if (x >= MOD) x -= MOD;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n;
    forn(_,n-1) {
        int u,v; cin >> u >> v;
        u--; v--;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    for (int x = 0; x <= n; x++) {
        comb[x][0] = 1;
        for (int y = 1; y <= x; y++) {
            comb[x][y] = comb[x-1][y-1] + comb[x-1][y];
            if (comb[x][y] >= MOD) comb[x][y] -= MOD;
        }
    }
    fact[0] = 1; for (int x = 1; x <= n; x++) fact[x] = ll(x) * fact[x-1] % MOD;

    dfs(0,-1);
    int c = 0;
    while (pref[c] != -1 && sz[pref[c]]*2 > n) c = pref[c];

    int sz = 1, ind = 1; dp[0][0] = 1;
    for (int v : adj[c]) {
        dfs(v,c);
        int n = ::sz[v];
        forn(k,n+1) {
            ll coef = (ll) fact[k] * comb[n][k] % MOD * comb[n][k] % MOD;
            forn(j,sz) add(dp[ind][j+k], (ll) dp[ind-1][j] * coef % MOD);
        }
        sz += n;
        ind++;
    }
    //forn(i,sz) cerr << dp[ind-1][i] << ' '; cerr << endl;

    ll ans = 0;
    forn(k,sz) {
        auto val = (ll) dp[ind-1][k] * fact[n-k] % MOD;
        if (k&1) ans -= val; else ans += val;
    }
    ans %= MOD; if (ans < 0) ans += MOD;
    cout << ans << endl;

    return 0;
}

```