#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

const long long INF = 1e18;
const ll mod = 1000000007;
ll N;
vector<ll> paths[5010];
ll sz[5010];
vector<ll> center;
vector<ll> inv, FactorialInv, Factorial;
ll beki(ll a, ll b){
    ll ret = 1 % mod;
    a %= mod;
    while(b) {
        if(b & 1LL) ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}
void init_combination(ll MAX){
    Factorial.resize(MAX + 1);
    FactorialInv.resize(MAX + 1);
    inv.resize(MAX + 1);
    Factorial[0] = 1;
    inv[0] = 1;
    for(int i = 1; i <= MAX; i++){
        Factorial[i] = Factorial[i - 1] * i % mod;
    }
    FactorialInv[MAX] = beki(Factorial[MAX], mod - 2);
    for(ll i = MAX - 1; i >= 0; i--) {
        FactorialInv[i] = FactorialInv[i+1] * (i+1) % mod;
    }
    for(int i = 1; i <= MAX; i++) {
        inv[i] = FactorialInv[i] * Factorial[i-1] % mod;
    }
}
ll combination(ll a, ll b){
    if((a == b) || (b == 0)){
        return 1;
    }
    if(a < b) return 0;
    if(b < 0) return 0;
    ll ans = Factorial[a] * FactorialInv[b] % mod;
    ans = ans * FactorialInv[a - b] % mod;
    return ans;
}

void dfs(int now, int from) {
    sz[now] = 1;
    for(auto to : paths[now]) {
        if(to == from) continue;
        dfs(to, now);
        sz[now] += sz[to];
    }
    bool iscenter = true;
    for(auto to : paths[now]) {
        if(to == from) {
            int p = N - sz[now];
            if(2 * p > N) iscenter = false;
        } else {
            if(2 * sz[to] > N) iscenter = false;
        }
    }
    if(iscenter) center.push_back(now);
}

vector<ll> v;
ll Prev[5005], Next[5005];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    init_combination(10000);
    cin >> N;
    for(int i = 0; i < N - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        paths[a].push_back(b);
        paths[b].push_back(a);
    }
    dfs(0, -1);
    //for(auto v : center) cerr << v << endl;
    if(center.size() == 2) {
        v.push_back(N / 2);
        v.push_back(N / 2);
    } else {
        dfs(center[0], -1);
        for(auto tmp : paths[center[0]]) {
            v.push_back(sz[tmp]);
        }
    }
    /*
    for(auto tmp : v) cerr << tmp << " ";
    cerr << endl;
    */
    Prev[0] = 1;
    for(auto tmp : v) {
        for(int i = 0; i <= N; i++) Next[i] = 0;
        for(ll num = 0; num <= tmp; num++) {
            ll factor = combination(tmp, num);
            factor *= Factorial[tmp];
            factor %= mod;
            factor *= FactorialInv[tmp - num];
            factor %= mod;
            for(int j = 0; j + num <= N; j++) {
                Next[j+num] += Prev[j] * factor;
                Next[j+num] %= mod;
            }
        }
        swap(Prev, Next);
    }
    ll ans = 0;
    for(int i = 0; i <= N; i++) {
        if(i & 1) ans += (mod - Prev[i]) * Factorial[N-i];
        else ans += Prev[i] * Factorial[N-i];
        ans %= mod;
    }
    cout << ans << endl;
    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 <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

const long long INF = 1e18;
const ll mod = 1000000007;
ll N;
vector<ll> paths[5010];
ll sz[5010];
vector<ll> center;
vector<ll> inv, FactorialInv, Factorial;
ll beki(ll a, ll b){
    ll ret = 1 % mod;
    a %= mod;
    while(b) {
        if(b & 1LL) ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}
void init_combination(ll MAX){
    Factorial.resize(MAX + 1);
    FactorialInv.resize(MAX + 1);
    inv.resize(MAX + 1);
    Factorial[0] = 1;
    inv[0] = 1;
    for(int i = 1; i <= MAX; i++){
        Factorial[i] = Factorial[i - 1] * i % mod;
    }
    FactorialInv[MAX] = beki(Factorial[MAX], mod - 2);
    for(ll i = MAX - 1; i >= 0; i--) {
        FactorialInv[i] = FactorialInv[i+1] * (i+1) % mod;
    }
    for(int i = 1; i <= MAX; i++) {
        inv[i] = FactorialInv[i] * Factorial[i-1] % mod;
    }
}
ll combination(ll a, ll b){
    if((a == b) || (b == 0)){
        return 1;
    }
    if(a < b) return 0;
    if(b < 0) return 0;
    ll ans = Factorial[a] * FactorialInv[b] % mod;
    ans = ans * FactorialInv[a - b] % mod;
    return ans;
}

void dfs(int now, int from) {
    sz[now] = 1;
    for(auto to : paths[now]) {
        if(to == from) continue;
        dfs(to, now);
        sz[now] += sz[to];
    }
    bool iscenter = true;
    for(auto to : paths[now]) {
        if(to == from) {
            int p = N - sz[now];
            if(2 * p > N) iscenter = false;
        } else {
            if(2 * sz[to] > N) iscenter = false;
        }
    }
    if(iscenter) center.push_back(now);
}

vector<ll> v;
ll Prev[5005], Next[5005];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    init_combination(10000);
    cin >> N;
    for(int i = 0; i < N - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        paths[a].push_back(b);
        paths[b].push_back(a);
    }
    dfs(0, -1);
    //for(auto v : center) cerr << v << endl;
    if(center.size() == 2) {
        v.push_back(N / 2);
        v.push_back(N / 2);
    } else {
        dfs(center[0], -1);
        for(auto tmp : paths[center[0]]) {
            v.push_back(sz[tmp]);
        }
    }
    /*
    for(auto tmp : v) cerr << tmp << " ";
    cerr << endl;
    */
    Prev[0] = 1;
    for(auto tmp : v) {
        for(int i = 0; i <= N; i++) Next[i] = 0;
        for(ll num = 0; num <= tmp; num++) {
            ll factor = combination(tmp, num);
            factor *= Factorial[tmp];
            factor %= mod;
            factor *= FactorialInv[tmp - num];
            factor %= mod;
            for(int j = 0; j + num <= N; j++) {
                Next[j+num] += Prev[j] * factor;
                Next[j+num] %= mod;
            }
        }
        swap(Prev, Next);
    }
    ll ans = 0;
    for(int i = 0; i <= N; i++) {
        if(i & 1) ans += (mod - Prev[i]) * Factorial[N-i];
        else ans += Prev[i] * Factorial[N-i];
        ans %= mod;
    }
    cout << ans << endl;
    return 0;
}

```