#pragma GCC optimize("O2,Ofast,inline,unroll-all-loops,-ffast-math")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
#define maxn 5010
#define ll long long
#define ull unsigned long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define pii pair<int, int>
#define pil pair<int, ll>
#define pll pair<ll, ll>
#define IL inline
#define ss system
using namespace std;

int sz[maxn], n, root = 0;
ll f[maxn][maxn], fac[maxn], ifac[maxn], ans = 0;
const ll p = 1e9 + 7;
vector<int> nxt[maxn];
template <class T> void read (T &x) {
  char ch = x = 0;
  bool fl = false;
  while (!isdigit(ch))
    fl |= ch == '-', ch = getchar();
  while (isdigit(ch))
    x = x * 10 + ch - '0', ch = getchar();
  x = fl ? -x : x;
}
void upd(ll &x, const ll &y) {
  x = (x + y) % p;
}
ll pw(ll a, ll b) {
  ll ret = 1;
  while (b) {
    if (b & 1)
      ret = ret * a % p;
    a = a * a % p, b >>= 1;
  }
  return ret;
}
ll A(int a, int b) {
  return a < b || b < 0 ? 0 : fac[a] * ifac[a - b] % p;
}
ll C(int a, int b) {
  return a < b || b < 0 ? 0 : fac[a] * ifac[b] % p * ifac[a - b] % p;
}
void dfs(int x, int fa) {
  int tmp = !(sz[x] = 1);
  for (auto &v : nxt[x]) {
    if (v != fa)
      dfs(v, x), sz[x] += sz[v], tmp = max(tmp, sz[v]);
  }
  tmp = max(tmp, n - sz[x]);
  if (tmp <= n / 2) {
    if (root && root != x)
      printf("%lld\n", fac[n / 2] * fac[n / 2] % p), exit(0);
    root = x;
  }
}
void init() {
  fac[0] = 1;
  for (int i = 1; i < maxn; i++) {
    fac[i] = fac[i - 1] * i % p;
  }
  ifac[maxn - 1] = pw(fac[maxn - 1], p - 2);
  for (int i = maxn - 2; ~i; i--) {
    ifac[i] = ifac[i + 1] * (i + 1) % p;
  }
}
int main() {
  read(n), init();
  for (int i = 1, u, v; i <= n - 1; i++) {
    read(u), read(v), nxt[u].pb(v), nxt[v].pb(u);
  }
  dfs(1, 0), dfs(root, 0);
  f[0][0] = 1;
  for (int i = 0, tot = 0; i < nxt[root].size(); i++) {
    int v = nxt[root][i];
    for (int j = 0; j <= tot; j++) {
      for (int k = 0; k <= sz[v]; k++) {
        upd(f[i + 1][j + k], f[i][j] * C(sz[v], k) % p * A(sz[v], k));
      }
    }
    tot += sz[v];
  }
  for (int i = 0; i < n; i++) {
    upd(ans, f[nxt[root].size()][i] * fac[n - i] % p * (i & 1 ? p - 1 : 1));
  }
  printf("%lld\n", ans);
  return 0;
}
### Prompt

Create a solution in cpp for 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
#pragma GCC optimize("O2,Ofast,inline,unroll-all-loops,-ffast-math")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
#define maxn 5010
#define ll long long
#define ull unsigned long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define pii pair<int, int>
#define pil pair<int, ll>
#define pll pair<ll, ll>
#define IL inline
#define ss system
using namespace std;

int sz[maxn], n, root = 0;
ll f[maxn][maxn], fac[maxn], ifac[maxn], ans = 0;
const ll p = 1e9 + 7;
vector<int> nxt[maxn];
template <class T> void read (T &x) {
  char ch = x = 0;
  bool fl = false;
  while (!isdigit(ch))
    fl |= ch == '-', ch = getchar();
  while (isdigit(ch))
    x = x * 10 + ch - '0', ch = getchar();
  x = fl ? -x : x;
}
void upd(ll &x, const ll &y) {
  x = (x + y) % p;
}
ll pw(ll a, ll b) {
  ll ret = 1;
  while (b) {
    if (b & 1)
      ret = ret * a % p;
    a = a * a % p, b >>= 1;
  }
  return ret;
}
ll A(int a, int b) {
  return a < b || b < 0 ? 0 : fac[a] * ifac[a - b] % p;
}
ll C(int a, int b) {
  return a < b || b < 0 ? 0 : fac[a] * ifac[b] % p * ifac[a - b] % p;
}
void dfs(int x, int fa) {
  int tmp = !(sz[x] = 1);
  for (auto &v : nxt[x]) {
    if (v != fa)
      dfs(v, x), sz[x] += sz[v], tmp = max(tmp, sz[v]);
  }
  tmp = max(tmp, n - sz[x]);
  if (tmp <= n / 2) {
    if (root && root != x)
      printf("%lld\n", fac[n / 2] * fac[n / 2] % p), exit(0);
    root = x;
  }
}
void init() {
  fac[0] = 1;
  for (int i = 1; i < maxn; i++) {
    fac[i] = fac[i - 1] * i % p;
  }
  ifac[maxn - 1] = pw(fac[maxn - 1], p - 2);
  for (int i = maxn - 2; ~i; i--) {
    ifac[i] = ifac[i + 1] * (i + 1) % p;
  }
}
int main() {
  read(n), init();
  for (int i = 1, u, v; i <= n - 1; i++) {
    read(u), read(v), nxt[u].pb(v), nxt[v].pb(u);
  }
  dfs(1, 0), dfs(root, 0);
  f[0][0] = 1;
  for (int i = 0, tot = 0; i < nxt[root].size(); i++) {
    int v = nxt[root][i];
    for (int j = 0; j <= tot; j++) {
      for (int k = 0; k <= sz[v]; k++) {
        upd(f[i + 1][j + k], f[i][j] * C(sz[v], k) % p * A(sz[v], k));
      }
    }
    tot += sz[v];
  }
  for (int i = 0; i < n; i++) {
    upd(ans, f[nxt[root].size()][i] * fac[n - i] % p * (i & 1 ? p - 1 : 1));
  }
  printf("%lld\n", ans);
  return 0;
}
```