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

using ll = long long;

const int N = 5005;
const ll M = ll(1e9) + 7;

int n, s[N], m;
ll a[N], d[N][N], p[N][N], r;
vector<int> e[N];

ll pw(ll n, ll k){
    if(!k) return 1;
    return pw(n * n % M, k / 2) * (k % 2 ? n : 1) % M;
}

int g(int x, int p){
    s[x] = 1;
    for(int i : e[x]) if(i != p) s[x] += g(i, x);
    return s[x];
}

int f(int x, int p, int t){
    for(int i : e[x])
        if(i != p && s[i] > t / 2) return f(i, x, t);
    return x;
}

int main(){
    scanf("%d", &n);
    for(int i = 0, x, y; i < n - 1; i++){
        scanf("%d%d", &x, &y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    int c = f(1, 0, g(1, 0));
    for(int i : e[c]) a[++m] = g(i, c);
    d[0][0] = 1;
    n--;
    for(int i = 1; i <= m; i++){
        ll t = 1, u = 1;
        for(int k = 0; k <= a[i]; k++){
            for(int j = k; j <= n; j++){
                d[i][j] = (d[i][j] + d[i - 1][j - k] * t) % M;
                p[i][j] = (p[i][j] + p[i - 1][j - k] * t) % M;
                if(k < a[i]) p[i][j] =
                    (p[i][j] + a[i] * a[i] * d[i - 1][j - k] % M * u) % M;
            }
            t = t * (a[i] - k) * (a[i] - k) % M * pw(k + 1, M - 2) % M;
            u = u * (a[i] - 1 - k) * (a[i] - 1 - k) % M * pw(k + 1, M - 2) % M;
        }
    }
    for(int i = 0, v = 1; i <= n; i++, v *= -1){
        ll q = 1;
        for(int j = 1; j <= n - i; j++) q = q * j % M;
        r = (r + M + v * (n + 1) * d[m][i] % M * q % M) % M;
        if(i) r = (r + M - v * p[m][i - 1] * q % M) % M;
    }
    printf("%lld\n", r);
}
### Prompt

Develop a solution in Cpp to the problem described below:

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;

using ll = long long;

const int N = 5005;
const ll M = ll(1e9) + 7;

int n, s[N], m;
ll a[N], d[N][N], p[N][N], r;
vector<int> e[N];

ll pw(ll n, ll k){
    if(!k) return 1;
    return pw(n * n % M, k / 2) * (k % 2 ? n : 1) % M;
}

int g(int x, int p){
    s[x] = 1;
    for(int i : e[x]) if(i != p) s[x] += g(i, x);
    return s[x];
}

int f(int x, int p, int t){
    for(int i : e[x])
        if(i != p && s[i] > t / 2) return f(i, x, t);
    return x;
}

int main(){
    scanf("%d", &n);
    for(int i = 0, x, y; i < n - 1; i++){
        scanf("%d%d", &x, &y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    int c = f(1, 0, g(1, 0));
    for(int i : e[c]) a[++m] = g(i, c);
    d[0][0] = 1;
    n--;
    for(int i = 1; i <= m; i++){
        ll t = 1, u = 1;
        for(int k = 0; k <= a[i]; k++){
            for(int j = k; j <= n; j++){
                d[i][j] = (d[i][j] + d[i - 1][j - k] * t) % M;
                p[i][j] = (p[i][j] + p[i - 1][j - k] * t) % M;
                if(k < a[i]) p[i][j] =
                    (p[i][j] + a[i] * a[i] * d[i - 1][j - k] % M * u) % M;
            }
            t = t * (a[i] - k) * (a[i] - k) % M * pw(k + 1, M - 2) % M;
            u = u * (a[i] - 1 - k) * (a[i] - 1 - k) % M * pw(k + 1, M - 2) % M;
        }
    }
    for(int i = 0, v = 1; i <= n; i++, v *= -1){
        ll q = 1;
        for(int j = 1; j <= n - i; j++) q = q * j % M;
        r = (r + M + v * (n + 1) * d[m][i] % M * q % M) % M;
        if(i) r = (r + M - v * p[m][i - 1] * q % M) % M;
    }
    printf("%lld\n", r);
}
```