#include <stdio.h>
#include <cstdlib>
#include <cassert>
#include <iostream>
#include <set>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <complex>
#include <map>
#include <queue>
#include <array>
#include <bitset>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef long double ld;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<pii> vii;
typedef vector<string> vs;
//typedef long long int;
const int mod = 1000000007;

ll mpow(ll x, ll n) {
  ll res = 1;
  while (n) {
    if (n & 1) res = res * x % mod;
    x = x * x % mod;
    n /= 2;
  }
  return res;
}

ll inv(ll x) {
  return mpow(x, mod-2);
}

vvi g;
vi sz;
vl fac(10000, 1);
vl invfac(10000, 1);

void dfs(int v, int p) {
  sz[v] = 1;
  for (int nv : g[v]) {
    if (nv == p) continue;
    dfs(nv, v);
    sz[v] += sz[nv];
  }
}

vl mul(const vl & a, const vl & b) {
  vl res(a.size() + b.size() - 1);
  for (int i = 0; i < a.size(); ++i) for (int j = 0; j < b.size(); ++j) {
    res[i+j] = (res[i+j] + a[i] * b[j]) % mod;
  }
  return res;
}

int main() {
  std::ios::sync_with_stdio(false); std::cin.tie(0);
  for (int i = 2; i < fac.size(); ++i) {
    fac[i] = fac[i-1] * i % mod;
    invfac[i] = inv(fac[i]);
  }
  int n;
  cin >> n;
  g.resize(n);
  for (int i = 0; i < n-1; ++i) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  for (int i = 0; i < n; ++i) {
    sz.assign(n, 0);
    dfs(i, -1);
    bool ok = 1, eq = 0;
    for (int v : g[i]) {
      if (sz[v] * 2 > n) {
        ok = 0;
      }
      if (sz[v] * 2 == n) eq = 1;
    }
    if (ok) {
      if (eq) {
        ll res = fac[n/2] * fac[n/2] % mod;
        cout << res << endl;
      } else {
        ll prod = 1;
        for (int v : g[i]) prod = prod * mpow(fac[sz[v]], 2) % mod;
        vl res(1, 1);
        for (int v : g[i]) {
          vl x(sz[v] + 1);
          for (int j = 0; j < x.size(); ++j) {
            x[j] = invfac[j] * mpow(invfac[sz[v] - j], 2) % mod;
          }
          res = mul(res, x);
        }
        ll sum = 0;
        for (int j = 0; j < res.size(); ++j) {
          int zn = j % 2 ? -1 : 1;
          sum = (sum + zn * res[j] * fac[n - j]) % mod;
        }
        sum = sum * prod % mod;
        cout << (sum % mod + mod) % mod << endl;
      }
      break;
    }
  }
  return 0;
}
### Prompt

Your challenge is to write 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 <stdio.h>
#include <cstdlib>
#include <cassert>
#include <iostream>
#include <set>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <complex>
#include <map>
#include <queue>
#include <array>
#include <bitset>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef long double ld;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<pii> vii;
typedef vector<string> vs;
//typedef long long int;
const int mod = 1000000007;

ll mpow(ll x, ll n) {
  ll res = 1;
  while (n) {
    if (n & 1) res = res * x % mod;
    x = x * x % mod;
    n /= 2;
  }
  return res;
}

ll inv(ll x) {
  return mpow(x, mod-2);
}

vvi g;
vi sz;
vl fac(10000, 1);
vl invfac(10000, 1);

void dfs(int v, int p) {
  sz[v] = 1;
  for (int nv : g[v]) {
    if (nv == p) continue;
    dfs(nv, v);
    sz[v] += sz[nv];
  }
}

vl mul(const vl & a, const vl & b) {
  vl res(a.size() + b.size() - 1);
  for (int i = 0; i < a.size(); ++i) for (int j = 0; j < b.size(); ++j) {
    res[i+j] = (res[i+j] + a[i] * b[j]) % mod;
  }
  return res;
}

int main() {
  std::ios::sync_with_stdio(false); std::cin.tie(0);
  for (int i = 2; i < fac.size(); ++i) {
    fac[i] = fac[i-1] * i % mod;
    invfac[i] = inv(fac[i]);
  }
  int n;
  cin >> n;
  g.resize(n);
  for (int i = 0; i < n-1; ++i) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  for (int i = 0; i < n; ++i) {
    sz.assign(n, 0);
    dfs(i, -1);
    bool ok = 1, eq = 0;
    for (int v : g[i]) {
      if (sz[v] * 2 > n) {
        ok = 0;
      }
      if (sz[v] * 2 == n) eq = 1;
    }
    if (ok) {
      if (eq) {
        ll res = fac[n/2] * fac[n/2] % mod;
        cout << res << endl;
      } else {
        ll prod = 1;
        for (int v : g[i]) prod = prod * mpow(fac[sz[v]], 2) % mod;
        vl res(1, 1);
        for (int v : g[i]) {
          vl x(sz[v] + 1);
          for (int j = 0; j < x.size(); ++j) {
            x[j] = invfac[j] * mpow(invfac[sz[v] - j], 2) % mod;
          }
          res = mul(res, x);
        }
        ll sum = 0;
        for (int j = 0; j < res.size(); ++j) {
          int zn = j % 2 ? -1 : 1;
          sum = (sum + zn * res[j] * fac[n - j]) % mod;
        }
        sum = sum * prod % mod;
        cout << (sum % mod + mod) % mod << endl;
      }
      break;
    }
  }
  return 0;
}
```