#include <bits/stdc++.h>

using namespace std;

template <class T> void mini(T &l, T r) {l = min(l, r);}
template <class T> void maxi(T &l, T r) {l = max(l, r);}

string to_string(string s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

using ll = long long;
const int N = 5010, B = 1e9 + 7;

int n;
vector <int> e[N];
ll ans;
int sz[N];
int mx[N];

ll mypw(ll a, int b) {
  ll ret = 1;
  while (b) {
    if (b & 1) ret = ret * a % B;
    b >>= 1;
    a = a * a % B;
  }
  return ret;
}

struct Modint {
  ll x;

  Modint(ll a = 0) {
    x = a % B;
    if (x < 0) x += B;
  }

  Modint inv() {
    return Modint(mypw(x, B - 2));
  }

  Modint operator+(Modint b) {
    return Modint(x + b.x);
  }

  Modint operator-(Modint b) {
    return Modint(x - b.x);
  }

  Modint operator*(Modint b) {
    return Modint(x * b.x);
  }

  Modint operator/(Modint b) {
    return (*this) * b.inv();
  }

};

string to_string(Modint a) {
  return to_string(a.x);
}

Modint f[N][N];
Modint fac[N], inv[N];

void upd(Modint &x, Modint y) {
  x = x + y;
}

void init() {
  fac[0] = 1;
  for (int i = 1; i < N; ++i) {
    fac[i] = fac[i - 1] * i;
  }
  for (int i = 0; i < N; ++i) {
    inv[i] = fac[i].inv();
  }
}

Modint C(int a, int b) {
  return fac[a] * inv[b] * inv[a - b];
}

void dfs(int u, int p = 0) {
  sz[u] = 1;
  int &mx = ::mx[u];
  for (auto v : e[u]) {
    if (v == p) continue;
    dfs(v, u);
    sz[u] += sz[v];
    mx = max(mx, sz[v]);
  }
  mx = max(mx, n - sz[u]);
}


void run() {
  init();

  cin >> n;
  for (int i = 1; i < n; ++i) {
    int x, y;
    cin >> x >> y;
    e[x].push_back(y);
    e[y].push_back(x);
  }

  dfs(1);

  int z = *min_element(mx + 1, mx + n + 1);
  debug(z);
  vector <int> cent;

  for (int i = 1; i <= n; ++i) if (mx[i] == z) {
    cent.push_back(i);
  }
  debug(cent);

  
  if ((int)cent.size() > 1) {
    cout << (fac[n / 2] * fac[n / 2]).x << endl;
    return;
  }
  
  dfs(cent.back());

  vector <int> vv;

  vv.push_back(0);
  for (auto v : e[cent.back()]) {
    vv.push_back(sz[v]);
  }
  
  debug(vv);
  int k = vv.size() - 1;

  f[0][0] = 1;
  int sum = 0;
  for (int i = 0; i < k; ++i) {
    sum += vv[i];
    for (int x = 0; x <= sum; ++x) {
      debug(f[i][x], i, x);
      for (int y = 0; y <= vv[i + 1]; ++y) {
        upd(f[i + 1][x + y], f[i][x] * C(vv[i + 1], y) * C(vv[i + 1], y) * fac[y]);
      }
    }
  }
  for (int x = 0; x < n; ++x) {
    debug(k, x, f[k][x]);
  }

  debug(C(5, 2));
  Modint ans = 0;
  int fl = 1;
  for (int i = 0; i < n; ++i) {
    upd(ans, fac[n - i] * f[k][i] * fl);
    debug(ans, fac[n - i], f[k][i]);
    fl *= -1;
  }

  cout << ans.x << endl;

}

int main() {
  run();
  return 0;
}

### Prompt

Please formulate 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;

template <class T> void mini(T &l, T r) {l = min(l, r);}
template <class T> void maxi(T &l, T r) {l = max(l, r);}

string to_string(string s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

using ll = long long;
const int N = 5010, B = 1e9 + 7;

int n;
vector <int> e[N];
ll ans;
int sz[N];
int mx[N];

ll mypw(ll a, int b) {
  ll ret = 1;
  while (b) {
    if (b & 1) ret = ret * a % B;
    b >>= 1;
    a = a * a % B;
  }
  return ret;
}

struct Modint {
  ll x;

  Modint(ll a = 0) {
    x = a % B;
    if (x < 0) x += B;
  }

  Modint inv() {
    return Modint(mypw(x, B - 2));
  }

  Modint operator+(Modint b) {
    return Modint(x + b.x);
  }

  Modint operator-(Modint b) {
    return Modint(x - b.x);
  }

  Modint operator*(Modint b) {
    return Modint(x * b.x);
  }

  Modint operator/(Modint b) {
    return (*this) * b.inv();
  }

};

string to_string(Modint a) {
  return to_string(a.x);
}

Modint f[N][N];
Modint fac[N], inv[N];

void upd(Modint &x, Modint y) {
  x = x + y;
}

void init() {
  fac[0] = 1;
  for (int i = 1; i < N; ++i) {
    fac[i] = fac[i - 1] * i;
  }
  for (int i = 0; i < N; ++i) {
    inv[i] = fac[i].inv();
  }
}

Modint C(int a, int b) {
  return fac[a] * inv[b] * inv[a - b];
}

void dfs(int u, int p = 0) {
  sz[u] = 1;
  int &mx = ::mx[u];
  for (auto v : e[u]) {
    if (v == p) continue;
    dfs(v, u);
    sz[u] += sz[v];
    mx = max(mx, sz[v]);
  }
  mx = max(mx, n - sz[u]);
}


void run() {
  init();

  cin >> n;
  for (int i = 1; i < n; ++i) {
    int x, y;
    cin >> x >> y;
    e[x].push_back(y);
    e[y].push_back(x);
  }

  dfs(1);

  int z = *min_element(mx + 1, mx + n + 1);
  debug(z);
  vector <int> cent;

  for (int i = 1; i <= n; ++i) if (mx[i] == z) {
    cent.push_back(i);
  }
  debug(cent);

  
  if ((int)cent.size() > 1) {
    cout << (fac[n / 2] * fac[n / 2]).x << endl;
    return;
  }
  
  dfs(cent.back());

  vector <int> vv;

  vv.push_back(0);
  for (auto v : e[cent.back()]) {
    vv.push_back(sz[v]);
  }
  
  debug(vv);
  int k = vv.size() - 1;

  f[0][0] = 1;
  int sum = 0;
  for (int i = 0; i < k; ++i) {
    sum += vv[i];
    for (int x = 0; x <= sum; ++x) {
      debug(f[i][x], i, x);
      for (int y = 0; y <= vv[i + 1]; ++y) {
        upd(f[i + 1][x + y], f[i][x] * C(vv[i + 1], y) * C(vv[i + 1], y) * fac[y]);
      }
    }
  }
  for (int x = 0; x < n; ++x) {
    debug(k, x, f[k][x]);
  }

  debug(C(5, 2));
  Modint ans = 0;
  int fl = 1;
  for (int i = 0; i < n; ++i) {
    upd(ans, fac[n - i] * f[k][i] * fl);
    debug(ans, fac[n - i], f[k][i]);
    fl *= -1;
  }

  cout << ans.x << endl;

}

int main() {
  run();
  return 0;
}

```