#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

const ll mod = 1000000007;
const int N = 10010;
ll fact[N], invf[N];

ll add(ll x, ll y){
    return (x+y)%mod;
}

ll mul(ll x, ll y){
    return (x%mod)*(y%mod)%mod;
}

ll powll(ll x, ll y){
    ll res = 1LL;
    while(y){
        if (y & 1LL)
            res *= x;
        res %= mod;
        x = (x*x) % mod;
        y >>= 1LL;
    }
    return res;
}

ll divll(ll x, ll y){
    return (x * powll(y,mod-2)) % mod;
}

ll nPr(ll n, ll r){
    if (n < r || r < 0) return 0;
    return mul(fact[n], invf[n-r]);
}

ll nCr(ll n, ll r){
    if (n < r || r < 0) return 0;
    return mul(mul(fact[n], invf[r]), invf[n-r]);
}

VI Centroid(VVI &graph){
    int n = graph.size();
    VI ret, sz(n);
    function<void (int, int)> dfs = [&](int now, int past){
        sz[now] = 1;
        bool is_centroid = true;
        for (int next : graph[now]){
            if (next == past) continue;
            dfs(next, now);
            sz[now] += sz[next];
            if (sz[next] > n / 2) is_centroid = false;
        }
        if (n - sz[now] > n / 2) is_centroid = false;
        if (is_centroid) ret.push_back(now);
    };
    dfs(0, -1);
    return ret;
}

int dfs(int now, int past, VVI &e){
    int ret = 1;
    for (int next : e[now]){
        if (next == past) continue;
        ret += dfs(next, now, e);
    }
    return ret;
}

ll dp[5010][5010];

int main() {
    int n;
    cin >> n;
    VVI e(n);
    REP(i,n-1){
        int u = in() - 1, v = in() - 1;
        e[u].push_back(v);
        e[v].push_back(u);
    }

    fact[0] = invf[0] = 1;
    FOR(i,1,N-1){
        fact[i] = (fact[i-1] * i) % mod;
        invf[i] = divll(invf[i-1], i);
    }

    VI cs = Centroid(e);

    if (cs.size() == 2){
        ll ans = fact[n / 2];
        ans = (ans * ans) % mod;
        cout << ans << endl;
        return 0;
    }

    int c = cs[0];
    VI a;
    for (int v : e[c]){
        a.push_back(dfs(v, c, e));
    }
    int k = a.size();

    dp[0][0] = 1;
    REP(i,k){
        REP(j,n){
            REP(s,a[i]+1){
                ll tmp = dp[i][j];
                tmp = (tmp * fact[s]) % mod;
                tmp = (tmp * nCr(a[i], s)) % mod;
                tmp = (tmp * nCr(a[i], s)) % mod;
                dp[i + 1][j + s] = (dp[i + 1][j + s] + tmp) % mod;
            }
        }
    }

    ll ans = 0;
    REP(i,n){
        ll tmp = (fact[n - i] * dp[k][i]) % mod;
        if (i % 2 == 0) ans = (ans + tmp) % mod;
        else ans = (ans - tmp + mod) % mod;
    }
    cout << ans << endl;

    return 0;
}
### Prompt

Your challenge is to write 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 <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

const ll mod = 1000000007;
const int N = 10010;
ll fact[N], invf[N];

ll add(ll x, ll y){
    return (x+y)%mod;
}

ll mul(ll x, ll y){
    return (x%mod)*(y%mod)%mod;
}

ll powll(ll x, ll y){
    ll res = 1LL;
    while(y){
        if (y & 1LL)
            res *= x;
        res %= mod;
        x = (x*x) % mod;
        y >>= 1LL;
    }
    return res;
}

ll divll(ll x, ll y){
    return (x * powll(y,mod-2)) % mod;
}

ll nPr(ll n, ll r){
    if (n < r || r < 0) return 0;
    return mul(fact[n], invf[n-r]);
}

ll nCr(ll n, ll r){
    if (n < r || r < 0) return 0;
    return mul(mul(fact[n], invf[r]), invf[n-r]);
}

VI Centroid(VVI &graph){
    int n = graph.size();
    VI ret, sz(n);
    function<void (int, int)> dfs = [&](int now, int past){
        sz[now] = 1;
        bool is_centroid = true;
        for (int next : graph[now]){
            if (next == past) continue;
            dfs(next, now);
            sz[now] += sz[next];
            if (sz[next] > n / 2) is_centroid = false;
        }
        if (n - sz[now] > n / 2) is_centroid = false;
        if (is_centroid) ret.push_back(now);
    };
    dfs(0, -1);
    return ret;
}

int dfs(int now, int past, VVI &e){
    int ret = 1;
    for (int next : e[now]){
        if (next == past) continue;
        ret += dfs(next, now, e);
    }
    return ret;
}

ll dp[5010][5010];

int main() {
    int n;
    cin >> n;
    VVI e(n);
    REP(i,n-1){
        int u = in() - 1, v = in() - 1;
        e[u].push_back(v);
        e[v].push_back(u);
    }

    fact[0] = invf[0] = 1;
    FOR(i,1,N-1){
        fact[i] = (fact[i-1] * i) % mod;
        invf[i] = divll(invf[i-1], i);
    }

    VI cs = Centroid(e);

    if (cs.size() == 2){
        ll ans = fact[n / 2];
        ans = (ans * ans) % mod;
        cout << ans << endl;
        return 0;
    }

    int c = cs[0];
    VI a;
    for (int v : e[c]){
        a.push_back(dfs(v, c, e));
    }
    int k = a.size();

    dp[0][0] = 1;
    REP(i,k){
        REP(j,n){
            REP(s,a[i]+1){
                ll tmp = dp[i][j];
                tmp = (tmp * fact[s]) % mod;
                tmp = (tmp * nCr(a[i], s)) % mod;
                tmp = (tmp * nCr(a[i], s)) % mod;
                dp[i + 1][j + s] = (dp[i + 1][j + s] + tmp) % mod;
            }
        }
    }

    ll ans = 0;
    REP(i,n){
        ll tmp = (fact[n - i] * dp[k][i]) % mod;
        if (i % 2 == 0) ans = (ans + tmp) % mod;
        else ans = (ans - tmp + mod) % mod;
    }
    cout << ans << endl;

    return 0;
}
```