#include <iostream>
#include <vector>
using namespace std;
int N;
vector <int> G[5005];
int Sz[5005], DP[5005][5005];
int C[5005][5005], root, Fact[5005];
const int MOD = 1000000007;
void precalcC()
{
    C[0][0] = 1;
    for(int i = 1; i <= N; i++)
        C[i][0] = 1;
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= i; j++)
        {
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
            if(C[i][j] >= MOD)
                C[i][j] -= MOD;
        }
}
void DFS(int node, int father)
{
    Sz[node] = 1;
    for(int i = 0; i < G[node].size(); i++)
    {
        int neighb = G[node][i];
        if(neighb == father)
            continue;
        DFS(neighb, node);
        Sz[node] += Sz[neighb];
    }
}
void findCentroid(int node, int father)
{
    bool centroid = 1;
    for(int i = 0; i < G[node].size(); i++)
    {
        int neighb = G[node][i];
        if(neighb == father)
            continue;
        if(Sz[neighb] >= (N + 1) / 2)
        {
            findCentroid(neighb, node);
            centroid = 0;
            break;
        }

    }
    if(centroid == 1)
    {
        root = node;
    }
}

void Case1()
{
    cout << (1LL * Fact[N / 2] * Fact[N / 2]) % MOD;
}
inline void Add(int& x, int y)
{
    x += y;
    if(x >= MOD)
        x -= MOD;
}
void Case2()
{
    int cnt = 0, s = 0;
    DP[0][0] = 1;
    int lim = G[root].size();
    for(int i = 1; i <= G[root].size(); i++)
    {
        int sz = Sz[G[root][i - 1]];
        for(int j = 0; j <= s; j++)
        {
            for(int k = 0; k <= sz; k++)
            {
                int aux = (1LL * C[sz][k] * C[sz][k]) % MOD;
                aux = (1LL * aux * Fact[k]) % MOD;
                Add(DP[i][j + k], (1LL * DP[i - 1][j] * aux) % MOD);
            }
        }
        s += sz;
    }
    int ans = 0;
    for(int i = 0; i <= N; i++)
    {
        int aux = (1LL * Fact[N - i] * DP[lim][i]) % MOD;
        if(i % 2 == 1)
            aux = MOD - aux;
        Add(ans, aux);
    }
    cout << ans << "\n";
}
void Read()
{
    cin >> N;
    for(int i = 1; i < N; i++)
    {
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}
int main()
{
    Read();
    Fact[0] = 1;
    for(int i = 1; i <= N; i++)
        Fact[i] = (1LL * Fact[i - 1] * i) % MOD;
    precalcC();
    DFS(1, 0);
    findCentroid(1, 0);
    DFS(root, 0);
    for(int i = 0; i < G[root].size(); i++)
    {
        int neighb = G[root][i];
        if(Sz[neighb] == N - Sz[neighb])
        {
            Case1();
            return 0;
        }
    }
    Case2();
    return 0;
}

### 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 <iostream>
#include <vector>
using namespace std;
int N;
vector <int> G[5005];
int Sz[5005], DP[5005][5005];
int C[5005][5005], root, Fact[5005];
const int MOD = 1000000007;
void precalcC()
{
    C[0][0] = 1;
    for(int i = 1; i <= N; i++)
        C[i][0] = 1;
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= i; j++)
        {
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
            if(C[i][j] >= MOD)
                C[i][j] -= MOD;
        }
}
void DFS(int node, int father)
{
    Sz[node] = 1;
    for(int i = 0; i < G[node].size(); i++)
    {
        int neighb = G[node][i];
        if(neighb == father)
            continue;
        DFS(neighb, node);
        Sz[node] += Sz[neighb];
    }
}
void findCentroid(int node, int father)
{
    bool centroid = 1;
    for(int i = 0; i < G[node].size(); i++)
    {
        int neighb = G[node][i];
        if(neighb == father)
            continue;
        if(Sz[neighb] >= (N + 1) / 2)
        {
            findCentroid(neighb, node);
            centroid = 0;
            break;
        }

    }
    if(centroid == 1)
    {
        root = node;
    }
}

void Case1()
{
    cout << (1LL * Fact[N / 2] * Fact[N / 2]) % MOD;
}
inline void Add(int& x, int y)
{
    x += y;
    if(x >= MOD)
        x -= MOD;
}
void Case2()
{
    int cnt = 0, s = 0;
    DP[0][0] = 1;
    int lim = G[root].size();
    for(int i = 1; i <= G[root].size(); i++)
    {
        int sz = Sz[G[root][i - 1]];
        for(int j = 0; j <= s; j++)
        {
            for(int k = 0; k <= sz; k++)
            {
                int aux = (1LL * C[sz][k] * C[sz][k]) % MOD;
                aux = (1LL * aux * Fact[k]) % MOD;
                Add(DP[i][j + k], (1LL * DP[i - 1][j] * aux) % MOD);
            }
        }
        s += sz;
    }
    int ans = 0;
    for(int i = 0; i <= N; i++)
    {
        int aux = (1LL * Fact[N - i] * DP[lim][i]) % MOD;
        if(i % 2 == 1)
            aux = MOD - aux;
        Add(ans, aux);
    }
    cout << ans << "\n";
}
void Read()
{
    cin >> N;
    for(int i = 1; i < N; i++)
    {
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}
int main()
{
    Read();
    Fact[0] = 1;
    for(int i = 1; i <= N; i++)
        Fact[i] = (1LL * Fact[i - 1] * i) % MOD;
    precalcC();
    DFS(1, 0);
    findCentroid(1, 0);
    DFS(root, 0);
    for(int i = 0; i < G[root].size(); i++)
    {
        int neighb = G[root][i];
        if(Sz[neighb] == N - Sz[neighb])
        {
            Case1();
            return 0;
        }
    }
    Case2();
    return 0;
}

```