#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

// modを法としたときの逆数を求める
void mod_inverse(int n, vector<long long>& inv, int mod)
{
    inv.assign(n+1, -1);
    inv[1] = 1;
    for(int i=2; i<=n; ++i)
        inv[i] = inv[mod % i] * (mod - mod / i) % mod;
}

// 階乗数の事前計算を用いた各種組合せ
class FactorialCalculation
{
private:
    const int mod;
    vector<long long> factorial;
    vector<long long> invFactorial;
public:
    FactorialCalculation(int n, int mod) : mod(mod)
    {
        factorial.resize(n+1, 1);
        invFactorial.resize(n+1, 1);
        vector<long long> inv;
        mod_inverse(n, inv, mod);
        for(int i=1; i<=n; ++i){
            factorial[i] = factorial[i-1] * i % mod;
            invFactorial[i] = invFactorial[i-1] * inv[i] % mod;
        }
    }
    long long getFactorial(int n){
        return factorial[n];
    }
    long long getInvFactorial(int n){
        return invFactorial[n];
    }
    long long getPermutation(int n, int r){
        if(n < r)
            return 0;
        return factorial[n] * invFactorial[n-r] % mod;
    }
    long long getCombination(int n, int r){
        if(n < r)
            return 0;
        return getPermutation(n, r) * invFactorial[r] % mod;
    }
    long long getHomogeneous(int n, int r){
        return getCombination(n+r-1, r);
    }
};

// 木の重心
int treeCentroid(const vector<vector<int> >& edges, vector<int>& centroid, int curr = 0, int prev = -1)
{
    int n = edges.size();
    int sum = 0;
    bool ok = true;
    for(int next : edges[curr]){
        if(next == prev)
            continue;
        int size = treeCentroid(edges, centroid, next, curr);
        sum += size;
        if(size > n / 2)
            ok = false;
    }

    if(ok && n - 1 - sum <= n / 2)
        centroid.push_back(curr);
    return sum + 1;
}

const int MOD = 1000000007;

int countSubTreeSize(const vector<vector<int> >& edges, int curr, int prev)
{
    int ans = 1;
    for(int next : edges[curr]){
        if(next == prev)
            continue;
        ans += countSubTreeSize(edges, next, curr);
    }
    return ans;
}

long long solve(const vector<vector<int> >& edges)
{
    int n = edges.size();
    FactorialCalculation fc(n, MOD);

    vector<int> centroid;
    treeCentroid(edges, centroid);
    if(centroid.size() == 2){
        long long ans = fc.getFactorial(n/2);
        ans *= ans;
        ans %= MOD;
        return ans;
    }

    vector<long long> dp(n, 0);
    dp[0] = 1;
    for(int node : edges[centroid[0]]){
        int cnt = countSubTreeSize(edges, node, centroid[0]);
        for(int i=n-1; i>=0; --i){
            for(int j=1; j<=cnt && i+j<n; ++j){
                long long tmp = fc.getCombination(cnt, j) * fc.getPermutation(cnt, j);
                tmp %= MOD;
                dp[i+j] += dp[i] * tmp;
                dp[i+j] %= MOD;
            }
        }
    }

    long long ans = fc.getFactorial(n);
    for(int i=1; i<n; ++i){
        long long tmp = dp[i] * fc.getFactorial(n - i);
        tmp %= MOD;
        if(i % 2 == 0)
            ans += tmp;
        else
            ans += MOD - tmp;
        ans %= MOD;
    }
    return ans;
}

int main()
{
    int n;
    cin >> n;
    vector<vector<int> > edges(n);
    for(int i=0; i<n-1; ++i){
        int x, y;
        cin >> x >> y;
        -- x;
        -- y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }

    cout << solve(edges) << 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
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

// modを法としたときの逆数を求める
void mod_inverse(int n, vector<long long>& inv, int mod)
{
    inv.assign(n+1, -1);
    inv[1] = 1;
    for(int i=2; i<=n; ++i)
        inv[i] = inv[mod % i] * (mod - mod / i) % mod;
}

// 階乗数の事前計算を用いた各種組合せ
class FactorialCalculation
{
private:
    const int mod;
    vector<long long> factorial;
    vector<long long> invFactorial;
public:
    FactorialCalculation(int n, int mod) : mod(mod)
    {
        factorial.resize(n+1, 1);
        invFactorial.resize(n+1, 1);
        vector<long long> inv;
        mod_inverse(n, inv, mod);
        for(int i=1; i<=n; ++i){
            factorial[i] = factorial[i-1] * i % mod;
            invFactorial[i] = invFactorial[i-1] * inv[i] % mod;
        }
    }
    long long getFactorial(int n){
        return factorial[n];
    }
    long long getInvFactorial(int n){
        return invFactorial[n];
    }
    long long getPermutation(int n, int r){
        if(n < r)
            return 0;
        return factorial[n] * invFactorial[n-r] % mod;
    }
    long long getCombination(int n, int r){
        if(n < r)
            return 0;
        return getPermutation(n, r) * invFactorial[r] % mod;
    }
    long long getHomogeneous(int n, int r){
        return getCombination(n+r-1, r);
    }
};

// 木の重心
int treeCentroid(const vector<vector<int> >& edges, vector<int>& centroid, int curr = 0, int prev = -1)
{
    int n = edges.size();
    int sum = 0;
    bool ok = true;
    for(int next : edges[curr]){
        if(next == prev)
            continue;
        int size = treeCentroid(edges, centroid, next, curr);
        sum += size;
        if(size > n / 2)
            ok = false;
    }

    if(ok && n - 1 - sum <= n / 2)
        centroid.push_back(curr);
    return sum + 1;
}

const int MOD = 1000000007;

int countSubTreeSize(const vector<vector<int> >& edges, int curr, int prev)
{
    int ans = 1;
    for(int next : edges[curr]){
        if(next == prev)
            continue;
        ans += countSubTreeSize(edges, next, curr);
    }
    return ans;
}

long long solve(const vector<vector<int> >& edges)
{
    int n = edges.size();
    FactorialCalculation fc(n, MOD);

    vector<int> centroid;
    treeCentroid(edges, centroid);
    if(centroid.size() == 2){
        long long ans = fc.getFactorial(n/2);
        ans *= ans;
        ans %= MOD;
        return ans;
    }

    vector<long long> dp(n, 0);
    dp[0] = 1;
    for(int node : edges[centroid[0]]){
        int cnt = countSubTreeSize(edges, node, centroid[0]);
        for(int i=n-1; i>=0; --i){
            for(int j=1; j<=cnt && i+j<n; ++j){
                long long tmp = fc.getCombination(cnt, j) * fc.getPermutation(cnt, j);
                tmp %= MOD;
                dp[i+j] += dp[i] * tmp;
                dp[i+j] %= MOD;
            }
        }
    }

    long long ans = fc.getFactorial(n);
    for(int i=1; i<n; ++i){
        long long tmp = dp[i] * fc.getFactorial(n - i);
        tmp %= MOD;
        if(i % 2 == 0)
            ans += tmp;
        else
            ans += MOD - tmp;
        ans %= MOD;
    }
    return ans;
}

int main()
{
    int n;
    cin >> n;
    vector<vector<int> > edges(n);
    for(int i=0; i<n-1; ++i){
        int x, y;
        cin >> x >> y;
        -- x;
        -- y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }

    cout << solve(edges) << endl;

    return 0;
}

```