#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb(x) push_back(x)
#define all(x) x.begin(), x.end()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = 1e9;
const ll INF = 1e18;
const ld EPS = 1e-10;

const int MAX_N = 1e5;
ll fac[MAX_N+1], ifac[MAX_N+1], inv[MAX_N+1];

ll mpow(ll x, ll n){
    ll res = 1, now = x;
    while(n > 0){
        if(n & 1) res *= now, res %= MOD;
        now *= now, now %= MOD;
        n >>= 1;
    }
    return res;
}

void init(){
    rep2(i, 1, MAX_N){
        inv[i] = mpow(i, MOD-2);
    }
    //i!とi!の逆元
    fac[0] = 1, ifac[0] = 1;
    rep2(i, 1, MAX_N){
        fac[i] = (fac[i-1]*i) % MOD;
        ifac[i] = (ifac[i-1]*inv[i]) % MOD;
    }
}

ll comb(int n, int k){
    ll c = fac[n];
    c *= ifac[n-k], c %= MOD;
    c *= ifac[k], c %= MOD;
    return c;
}

ll perm(int n, int k){
    return(fac[n]*ifac[n-k])%MOD;
}

const int MAX_V = 5e3;
vector<int> es[MAX_V];
int subtree_size[MAX_V], max_size[MAX_V];

int dfs(int now, int pre, int size){
    int m = 0, s = 1;
    for(auto &e: es[now]){
        if(e == pre) continue;
        int tmp = dfs(e, now, size);
        s += tmp;
        m = max(m, tmp);
    }
    m = max(m, size-s);
    max_size[now] = m;
    subtree_size[now] = s;
    return s;
}

int main(){
    init();
    int N; cin >> N;
    rep(i, N-1){
        int u, v; cin >> u >> v; u--, v--;
        es[u].pb(v), es[v].pb(u);
    }
    dfs(0, -1, N);
    int g = -1;
    rep(i, N){
        if(max_size[i] <= N/2){
            if(g == -1) g = i;
            else{
                cout << (fac[N/2]*fac[N/2]) % MOD << endl;
                return 0;
            }
        }
    }
    vector<int> v;
    for(auto &e: es[g]) v.pb(dfs(e, g, N));
    int n = v.size();
    ll dp[n+1][N];
    fill(dp[0], dp[n+1], 0);
    dp[0][0] = 1;
    rep(i, n){
        rep(j, N){
            rep(k, v[i]+1){
                if(j+k >= N) break;
                dp[i+1][j+k] += dp[i][j]*((comb(v[i], k)*perm(v[i], k)) % MOD);
                dp[i+1][j+k] %= MOD;
            }
        }
    }
    ll ans = 0;
    rep(i, N){
        ll tmp = (fac[N-i]*dp[n][i]) % MOD;
        if(i&1) ans += MOD-tmp;
        else ans += tmp;
        ans %= MOD;
    }
    cout << ans << endl;
}
### 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
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb(x) push_back(x)
#define all(x) x.begin(), x.end()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = 1e9;
const ll INF = 1e18;
const ld EPS = 1e-10;

const int MAX_N = 1e5;
ll fac[MAX_N+1], ifac[MAX_N+1], inv[MAX_N+1];

ll mpow(ll x, ll n){
    ll res = 1, now = x;
    while(n > 0){
        if(n & 1) res *= now, res %= MOD;
        now *= now, now %= MOD;
        n >>= 1;
    }
    return res;
}

void init(){
    rep2(i, 1, MAX_N){
        inv[i] = mpow(i, MOD-2);
    }
    //i!とi!の逆元
    fac[0] = 1, ifac[0] = 1;
    rep2(i, 1, MAX_N){
        fac[i] = (fac[i-1]*i) % MOD;
        ifac[i] = (ifac[i-1]*inv[i]) % MOD;
    }
}

ll comb(int n, int k){
    ll c = fac[n];
    c *= ifac[n-k], c %= MOD;
    c *= ifac[k], c %= MOD;
    return c;
}

ll perm(int n, int k){
    return(fac[n]*ifac[n-k])%MOD;
}

const int MAX_V = 5e3;
vector<int> es[MAX_V];
int subtree_size[MAX_V], max_size[MAX_V];

int dfs(int now, int pre, int size){
    int m = 0, s = 1;
    for(auto &e: es[now]){
        if(e == pre) continue;
        int tmp = dfs(e, now, size);
        s += tmp;
        m = max(m, tmp);
    }
    m = max(m, size-s);
    max_size[now] = m;
    subtree_size[now] = s;
    return s;
}

int main(){
    init();
    int N; cin >> N;
    rep(i, N-1){
        int u, v; cin >> u >> v; u--, v--;
        es[u].pb(v), es[v].pb(u);
    }
    dfs(0, -1, N);
    int g = -1;
    rep(i, N){
        if(max_size[i] <= N/2){
            if(g == -1) g = i;
            else{
                cout << (fac[N/2]*fac[N/2]) % MOD << endl;
                return 0;
            }
        }
    }
    vector<int> v;
    for(auto &e: es[g]) v.pb(dfs(e, g, N));
    int n = v.size();
    ll dp[n+1][N];
    fill(dp[0], dp[n+1], 0);
    dp[0][0] = 1;
    rep(i, n){
        rep(j, N){
            rep(k, v[i]+1){
                if(j+k >= N) break;
                dp[i+1][j+k] += dp[i][j]*((comb(v[i], k)*perm(v[i], k)) % MOD);
                dp[i+1][j+k] %= MOD;
            }
        }
    }
    ll ans = 0;
    rep(i, N){
        ll tmp = (fac[N-i]*dp[n][i]) % MOD;
        if(i&1) ans += MOD-tmp;
        else ans += tmp;
        ans %= MOD;
    }
    cout << ans << endl;
}
```