#include <bits/stdc++.h>
using namespace std;
const int N = 5010, mod = 1e9 + 7;
int nt[N << 1], to[N << 1], head[N], cnt = 0;

void add(int x, int y) {
  to[++cnt] = y;
  nt[cnt] = head[x];
  head[x] = cnt;
}

int n, s[N], sz[N];
void predfs(int u, int fa) {
  sz[u] = 1;
  for(int i = head[u]; i; i = nt[i]) {
    if(to[i] != fa) {
      predfs(to[i], u);
      sz[u] += sz[to[i]];
      s[u] = max(s[u], sz[to[i]]);
    }
  }
  s[u] = max(s[u], n - sz[u]);
}

int ny[N], jc[N];
int pls(int x, int y) {
  return (x += y) >= mod ? x - mod : x;
}

void Add(int &x, int y) {
  x = pls(x, y);
}

int sub(int x, int y) {
  return (x -= y) < 0 ? x + mod : x;
}

void Sub(int &x, int y) {
  x = sub(x, y);
}

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

void Mul(int &x, int y) {
  x = mul(x, y);
}

int q_pow(int x, int y) {
  int ans = 1;
  for(; y; y >>= 1) {
    if(y & 1) Mul(ans, x);
    Mul(x, x);
  }
  return ans;
}

int C(int x, int y) {
  if(x < y) return 0;
  int pos = mul(jc[x], mul(ny[y], ny[x - y]));
  return pos;
}

void init() {
  jc[0] = 1;
  for(int i = 1; i < N; ++i)
    jc[i] = mul(jc[i - 1], i);
  ny[N - 1] = q_pow(jc[N - 1], mod - 2);
  for(int i = N - 2; i >= 0; --i)
    ny[i] = mul(ny[i + 1], i + 1);
}

int val[N], f[N];
int main() {
  init();
  scanf("%d", &n);
  for(int i = 2, x, y; i <= n; ++i) {
    scanf("%d%d", &x, &y);
    add(x, y), add(y, x);
  }
  predfs(1, 0);
  int zx = 0;
  for(int i = 1; i <= n; ++i) {
    if(!zx || s[zx] > s[i]) zx = i;
  }
//  printf("zx = %d\n", zx);
  if(n % 2 == 0 && s[zx] == n / 2) {
    printf("%d\n", mul(jc[n / 2], jc[n / 2]));
    exit(0);
  }
  int tot = 0;
  for(int i = head[zx]; i; i = nt[i]) {
    if(sz[to[i]] < sz[zx]) val[++tot] = sz[to[i]];
  }
  if(zx != 1) val[++tot] = n - sz[zx];
  int now = 0;
  f[0] = 1;
  for(int i = 1; i <= tot; ++i) {
    for(int v = now + val[i]; v >= 1; --v) {
      for(int t = 1; t <= val[i]; ++t) {
        if(v < t) break;
        Add(f[v], mul(mul(C(val[i], t), C(val[i], t)), mul(jc[t], f[v - t])));
      }
    }
    now += val[i];
  }
  int ans = 0;
  for(int i = 0; i < n; ++i) {
//    printf("f[%d] = %d\n", i, f[i]);
    if(i & 1) Sub(ans, mul(f[i], jc[n - i]));
    else Add(ans, mul(f[i], jc[n - i]));
  }
  printf("%d\n", ans);
  return 0;
}
### Prompt

Generate 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 <bits/stdc++.h>
using namespace std;
const int N = 5010, mod = 1e9 + 7;
int nt[N << 1], to[N << 1], head[N], cnt = 0;

void add(int x, int y) {
  to[++cnt] = y;
  nt[cnt] = head[x];
  head[x] = cnt;
}

int n, s[N], sz[N];
void predfs(int u, int fa) {
  sz[u] = 1;
  for(int i = head[u]; i; i = nt[i]) {
    if(to[i] != fa) {
      predfs(to[i], u);
      sz[u] += sz[to[i]];
      s[u] = max(s[u], sz[to[i]]);
    }
  }
  s[u] = max(s[u], n - sz[u]);
}

int ny[N], jc[N];
int pls(int x, int y) {
  return (x += y) >= mod ? x - mod : x;
}

void Add(int &x, int y) {
  x = pls(x, y);
}

int sub(int x, int y) {
  return (x -= y) < 0 ? x + mod : x;
}

void Sub(int &x, int y) {
  x = sub(x, y);
}

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

void Mul(int &x, int y) {
  x = mul(x, y);
}

int q_pow(int x, int y) {
  int ans = 1;
  for(; y; y >>= 1) {
    if(y & 1) Mul(ans, x);
    Mul(x, x);
  }
  return ans;
}

int C(int x, int y) {
  if(x < y) return 0;
  int pos = mul(jc[x], mul(ny[y], ny[x - y]));
  return pos;
}

void init() {
  jc[0] = 1;
  for(int i = 1; i < N; ++i)
    jc[i] = mul(jc[i - 1], i);
  ny[N - 1] = q_pow(jc[N - 1], mod - 2);
  for(int i = N - 2; i >= 0; --i)
    ny[i] = mul(ny[i + 1], i + 1);
}

int val[N], f[N];
int main() {
  init();
  scanf("%d", &n);
  for(int i = 2, x, y; i <= n; ++i) {
    scanf("%d%d", &x, &y);
    add(x, y), add(y, x);
  }
  predfs(1, 0);
  int zx = 0;
  for(int i = 1; i <= n; ++i) {
    if(!zx || s[zx] > s[i]) zx = i;
  }
//  printf("zx = %d\n", zx);
  if(n % 2 == 0 && s[zx] == n / 2) {
    printf("%d\n", mul(jc[n / 2], jc[n / 2]));
    exit(0);
  }
  int tot = 0;
  for(int i = head[zx]; i; i = nt[i]) {
    if(sz[to[i]] < sz[zx]) val[++tot] = sz[to[i]];
  }
  if(zx != 1) val[++tot] = n - sz[zx];
  int now = 0;
  f[0] = 1;
  for(int i = 1; i <= tot; ++i) {
    for(int v = now + val[i]; v >= 1; --v) {
      for(int t = 1; t <= val[i]; ++t) {
        if(v < t) break;
        Add(f[v], mul(mul(C(val[i], t), C(val[i], t)), mul(jc[t], f[v - t])));
      }
    }
    now += val[i];
  }
  int ans = 0;
  for(int i = 0; i < n; ++i) {
//    printf("f[%d] = %d\n", i, f[i]);
    if(i & 1) Sub(ans, mul(f[i], jc[n - i]));
    else Add(ans, mul(f[i], jc[n - i]));
  }
  printf("%d\n", ans);
  return 0;
}
```