#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int N;
vector<int> G[50010];
int sub[50010];
ll F[50010] = {1};
ll R[50010];
ll mod = 1000000007;
ll dp[5010][5010];

int sub_size(int v,int p)
{
    int res = 1;
    for(int i = 0; i < G[v].size(); i++)if(p != G[v][i])res += sub_size(G[v][i],v);
    return sub[v] = res;
}

ll con(int a,int b)
{
    return F[a] * R[a - b] % mod * R[b] % mod;
}

ll pow_mod(ll a,ll b)
{
    if(b == 0)return 1;
    ll res = pow_mod(a * a % mod, b / 2);
    if(b & 1)res = res * a % mod;
    return res;
}

int main()
{
    scanf("%d",&N);
    for(int i = 0; i < N - 1; i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        G[a].push_back(b);
        G[b].push_back(a);
    }

    for(int i = 1; i < 50010; i++)F[i] = F[i - 1] * i % mod;
    for(int i = 0; i < 50010; i++)R[i] = pow_mod(F[i],mod - 2);

    for(int i = 1; i <= N; i++)
    {
        for(int j = 0; j < G[i].size(); j++)
        {
            if(sub_size(i,G[i][j]) == sub_size(G[i][j],i))
            {
                printf("%lld\n",F[N / 2] * F[N / 2] % mod);
                return 0;
            }
        }
    }

    int c = 0,MIN = 1001001001;
    for(int i = 1; i <= N; i++)
    {
        int MAX = 0;
        for(int j = 0; j < G[i].size(); j++)MAX = max(MAX,sub_size(G[i][j],i));
        if(MIN > MAX)
        {
            c = i;
            MIN = MAX;
        }
    }

    dp[0][0] = 1;
    for(int i = 0; i < G[c].size(); i++)
    {
        for(int j = 0; j <= N; j++)
        {
            int m = sub_size(G[c][i],c);
            for(int k = 0; k <= m; k++)
            {
                if(j + k > N)continue;
                dp[i + 1][j + k] += dp[i][j] * con(m,k) % mod * con(m,k) % mod * F[k] % mod;
                dp[i + 1][j + k] %= mod;
            }
        }
    }

    ll ans = 0;
    for(int i = 0; i <= N; i++)
    {
        ll tmp = dp[G[c].size()][i] * F[N - i] % mod;
        if(i % 2)ans -= tmp;
        else ans += tmp;
        ans = (ans + mod) % mod;
    }

    printf("%lld\n",ans);
    return 0;
}

### Prompt

In CPP, your task is to solve 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;

typedef long long ll;

int N;
vector<int> G[50010];
int sub[50010];
ll F[50010] = {1};
ll R[50010];
ll mod = 1000000007;
ll dp[5010][5010];

int sub_size(int v,int p)
{
    int res = 1;
    for(int i = 0; i < G[v].size(); i++)if(p != G[v][i])res += sub_size(G[v][i],v);
    return sub[v] = res;
}

ll con(int a,int b)
{
    return F[a] * R[a - b] % mod * R[b] % mod;
}

ll pow_mod(ll a,ll b)
{
    if(b == 0)return 1;
    ll res = pow_mod(a * a % mod, b / 2);
    if(b & 1)res = res * a % mod;
    return res;
}

int main()
{
    scanf("%d",&N);
    for(int i = 0; i < N - 1; i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        G[a].push_back(b);
        G[b].push_back(a);
    }

    for(int i = 1; i < 50010; i++)F[i] = F[i - 1] * i % mod;
    for(int i = 0; i < 50010; i++)R[i] = pow_mod(F[i],mod - 2);

    for(int i = 1; i <= N; i++)
    {
        for(int j = 0; j < G[i].size(); j++)
        {
            if(sub_size(i,G[i][j]) == sub_size(G[i][j],i))
            {
                printf("%lld\n",F[N / 2] * F[N / 2] % mod);
                return 0;
            }
        }
    }

    int c = 0,MIN = 1001001001;
    for(int i = 1; i <= N; i++)
    {
        int MAX = 0;
        for(int j = 0; j < G[i].size(); j++)MAX = max(MAX,sub_size(G[i][j],i));
        if(MIN > MAX)
        {
            c = i;
            MIN = MAX;
        }
    }

    dp[0][0] = 1;
    for(int i = 0; i < G[c].size(); i++)
    {
        for(int j = 0; j <= N; j++)
        {
            int m = sub_size(G[c][i],c);
            for(int k = 0; k <= m; k++)
            {
                if(j + k > N)continue;
                dp[i + 1][j + k] += dp[i][j] * con(m,k) % mod * con(m,k) % mod * F[k] % mod;
                dp[i + 1][j + k] %= mod;
            }
        }
    }

    ll ans = 0;
    for(int i = 0; i <= N; i++)
    {
        ll tmp = dp[G[c].size()][i] * F[N - i] % mod;
        if(i % 2)ans -= tmp;
        else ans += tmp;
        ans = (ans + mod) % mod;
    }

    printf("%lld\n",ans);
    return 0;
}

```