#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;

const double EPS = 1e-10;
const ll INF = 100000000;
const ll MOD = 1000000007;

int n;
int si[5000], par[5000];
vector<int> e[5000];
vector<int> vec;
ll ans = 0;
ll dp[5001][5001];

vector<ll> pre[5001];
ll kai[5001];

ll mod_pow(ll x, ll y) {
    ll ret = 1;
    while (y) {
        if (y&1) ret = ret * x % MOD;
        x = x * x % MOD;
        y /= 2;
    }
    return ret;
}

void pre_calc() {
    kai[0] = 1;
    for (ll i = 1; i <= 5000; i++) {
        kai[i] = kai[i-1] * i % MOD;
    }
    rep(i,vec.size()) {
        pre[i].resize(vec[i]+1);
        pre[i][0] = 1;
        for (int j = 1; j <= vec[i]; j++) {
            pre[i][j] = kai[vec[i]] * mod_pow(kai[j], MOD-2) % MOD;
            pre[i][j] = pre[i][j] * mod_pow(kai[vec[i]-j], MOD-2) % MOD;
            pre[i][j] = pre[i][j] * pre[i][j] % MOD;
            pre[i][j] = pre[i][j] * kai[j] % MOD;
        }
    }
}

void dfs(int v) {
    rep(i,e[v].size()) {
        if (e[v][i] == par[v]) continue;
        par[e[v][i]] = v;
        dfs(e[v][i]);
    }
    si[v] = 1;
    rep(i,e[v].size()) {
        si[v] += si[e[v][i]];
    }
}

int main(){
    cin >> n;
    rep(i,n-1) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(0);
    int center = -1;
    rep(i,n) {
        bool ok = true;
        rep(j,e[i].size()) {
            if (e[i][j] == par[i]) {
                if (n-si[i] >= (n+1)/2) {
                    ok = false;
                    break;
                }
            } else {
                if (si[e[i][j]] >= (n+1)/2) {
                    ok = false;
                    break;
                }
            }
        }
        if (ok) {
            center = i;
            break;
        }
    }
    if (center == -1) {
        ans = 1;
        for (ll i = 1; i <= n/2; i++) {
            ans = ans * i % MOD;
        }
        ans = ans * ans % MOD;
        cout << ans << endl;
        return 0;
    }
    rep(i,e[center].size()) {
        if (e[center][i] == par[center]) {
            vec.push_back(n-si[center]);
        } else {
            vec.push_back(si[e[center][i]]);
        }
    }
    pre_calc();
    
    /*
    rep(i,vec.size()) {
        rep(j,pre[i].size()) {
            cout << pre[i][j] << " ";
        }
        cout << endl;
    }
    */
    
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    rep(i,vec.size()) {
        rep(j,n) {
            rep(k,vec[i]+1) {
                if (j-k < 0) break;
                dp[i+1][j] += (dp[i][j-k]*pre[i][k])%MOD;
            }
            dp[i+1][j] %= MOD;
        }
    }
    /*
    rep(i,n+1) {
        rep(j,n+1) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    */
    ans = 0;
    rep(i,n) {
        ll adder = (i%2==0?1LL:-1LL) * kai[n-i] * dp[vec.size()][i]%MOD;
        ans = (ans+adder)%MOD;
    }
    cout << (ans+MOD)%MOD << endl;
}































### Prompt

In CPP, your task is to solve 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>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;

const double EPS = 1e-10;
const ll INF = 100000000;
const ll MOD = 1000000007;

int n;
int si[5000], par[5000];
vector<int> e[5000];
vector<int> vec;
ll ans = 0;
ll dp[5001][5001];

vector<ll> pre[5001];
ll kai[5001];

ll mod_pow(ll x, ll y) {
    ll ret = 1;
    while (y) {
        if (y&1) ret = ret * x % MOD;
        x = x * x % MOD;
        y /= 2;
    }
    return ret;
}

void pre_calc() {
    kai[0] = 1;
    for (ll i = 1; i <= 5000; i++) {
        kai[i] = kai[i-1] * i % MOD;
    }
    rep(i,vec.size()) {
        pre[i].resize(vec[i]+1);
        pre[i][0] = 1;
        for (int j = 1; j <= vec[i]; j++) {
            pre[i][j] = kai[vec[i]] * mod_pow(kai[j], MOD-2) % MOD;
            pre[i][j] = pre[i][j] * mod_pow(kai[vec[i]-j], MOD-2) % MOD;
            pre[i][j] = pre[i][j] * pre[i][j] % MOD;
            pre[i][j] = pre[i][j] * kai[j] % MOD;
        }
    }
}

void dfs(int v) {
    rep(i,e[v].size()) {
        if (e[v][i] == par[v]) continue;
        par[e[v][i]] = v;
        dfs(e[v][i]);
    }
    si[v] = 1;
    rep(i,e[v].size()) {
        si[v] += si[e[v][i]];
    }
}

int main(){
    cin >> n;
    rep(i,n-1) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(0);
    int center = -1;
    rep(i,n) {
        bool ok = true;
        rep(j,e[i].size()) {
            if (e[i][j] == par[i]) {
                if (n-si[i] >= (n+1)/2) {
                    ok = false;
                    break;
                }
            } else {
                if (si[e[i][j]] >= (n+1)/2) {
                    ok = false;
                    break;
                }
            }
        }
        if (ok) {
            center = i;
            break;
        }
    }
    if (center == -1) {
        ans = 1;
        for (ll i = 1; i <= n/2; i++) {
            ans = ans * i % MOD;
        }
        ans = ans * ans % MOD;
        cout << ans << endl;
        return 0;
    }
    rep(i,e[center].size()) {
        if (e[center][i] == par[center]) {
            vec.push_back(n-si[center]);
        } else {
            vec.push_back(si[e[center][i]]);
        }
    }
    pre_calc();
    
    /*
    rep(i,vec.size()) {
        rep(j,pre[i].size()) {
            cout << pre[i][j] << " ";
        }
        cout << endl;
    }
    */
    
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    rep(i,vec.size()) {
        rep(j,n) {
            rep(k,vec[i]+1) {
                if (j-k < 0) break;
                dp[i+1][j] += (dp[i][j-k]*pre[i][k])%MOD;
            }
            dp[i+1][j] %= MOD;
        }
    }
    /*
    rep(i,n+1) {
        rep(j,n+1) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    */
    ans = 0;
    rep(i,n) {
        ll adder = (i%2==0?1LL:-1LL) * kai[n-i] * dp[vec.size()][i]%MOD;
        ans = (ans+adder)%MOD;
    }
    cout << (ans+MOD)%MOD << endl;
}































```