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

using I = long long;
const I M = 1e9 + 7;

class Combinatorics {
 public:
  Combinatorics(I N) : fact(N + 1, 1), inv(N + 1, 1), finv(N + 1, 1) {
    for(I i = 2; i <= N; ++i) {
      fact[i] = fact[i - 1] * i % M;
      inv[i]  = inv[M % i] * (M - M / i) % M;
      finv[i] = finv[i - 1] * inv[i] % M;
    }
  }
  I factorial(I n) {return fact[n];}
  I permutation(I n, I r) {return fact[n] * finv[n - r] % M;}
  I combination(I n, I r) {return permutation(n, r) * finv[r] % M;}
 private:
  std::vector<I> fact, inv, finv;
};

using Size = int;
using Vertex = int;
using Weight = long long;
struct Edge {Vertex from, to; Weight weight;};
using Graph = vector<vector<Edge>>;

I centroid(const Graph& G) {
  I N = G.size();
  vector<Vertex> C;
  vector<Size> size(N, 1);
  vector<vector<I>> S(N, vector<I>(N));
  function<Size(Vertex, Vertex)> dfs = [&](Vertex cur, Vertex pre) {
    auto ok = true;
    for(auto e: G[cur]) if(e.to != pre) {
      size[cur] += dfs(e.to, e.from);
      if(N / 2 < size[e.to]) ok = false;
    }
    if(N / 2 < N - size[cur]) ok = false;
    if(ok) C.emplace_back(cur);
    if(ok) {
      S[cur][pre] = N - size[cur];
      for(auto e: G[cur]) if(e.to != pre) S[cur][e.to] = size[e.to];
    }
    return size[cur];
  };
  dfs(0, 0);

  Combinatorics X(N);

  if(C.size() == 2) return X.factorial(S[C[0]][C[1]]) * X.factorial(S[C[1]][C[0]]) % M;

  I res = 0;
  vector<I> T; // sizes of each connected component on the graph removing the centroid
  for(auto e: G[C[0]]) T.emplace_back(S[C[0]][e.to]);

  vector<vector<I>> dp(T.size() + 1, vector<I>(N + 1));
  dp[0][0] = 1;
  for(auto i = 0; i < T.size(); ++i) {
    for(I x = 0; x <= T[i]; ++x) {
      for(I k = 0; k + x <= N; ++k) {
        (dp[i + 1][k + x] += (dp[i][k] * X.combination(T[i], x) % M) * X.permutation(T[i], x) % M) %= M;
      }
    }
  }

  I sign = 1;
  for(I k = 0; k <= N; ++k) {
    (res += sign * X.factorial(N - k) * dp[T.size()][k] % M) %= M;
    (res += M) %= M;
    sign *= -1;
  }
  return res;
}

int main() {
  Size N;
  cin >> N;
  Graph G(N);
  for(auto i = 1; i < N; ++i) {
    Vertex x, y;
    cin >> x >> y; --x; --y;
    G[x].push_back({x, y});
    G[y].push_back({y, x});
  }
  cout << centroid(G) << endl;
}

### Prompt

Please create a solution in CPP 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;

using I = long long;
const I M = 1e9 + 7;

class Combinatorics {
 public:
  Combinatorics(I N) : fact(N + 1, 1), inv(N + 1, 1), finv(N + 1, 1) {
    for(I i = 2; i <= N; ++i) {
      fact[i] = fact[i - 1] * i % M;
      inv[i]  = inv[M % i] * (M - M / i) % M;
      finv[i] = finv[i - 1] * inv[i] % M;
    }
  }
  I factorial(I n) {return fact[n];}
  I permutation(I n, I r) {return fact[n] * finv[n - r] % M;}
  I combination(I n, I r) {return permutation(n, r) * finv[r] % M;}
 private:
  std::vector<I> fact, inv, finv;
};

using Size = int;
using Vertex = int;
using Weight = long long;
struct Edge {Vertex from, to; Weight weight;};
using Graph = vector<vector<Edge>>;

I centroid(const Graph& G) {
  I N = G.size();
  vector<Vertex> C;
  vector<Size> size(N, 1);
  vector<vector<I>> S(N, vector<I>(N));
  function<Size(Vertex, Vertex)> dfs = [&](Vertex cur, Vertex pre) {
    auto ok = true;
    for(auto e: G[cur]) if(e.to != pre) {
      size[cur] += dfs(e.to, e.from);
      if(N / 2 < size[e.to]) ok = false;
    }
    if(N / 2 < N - size[cur]) ok = false;
    if(ok) C.emplace_back(cur);
    if(ok) {
      S[cur][pre] = N - size[cur];
      for(auto e: G[cur]) if(e.to != pre) S[cur][e.to] = size[e.to];
    }
    return size[cur];
  };
  dfs(0, 0);

  Combinatorics X(N);

  if(C.size() == 2) return X.factorial(S[C[0]][C[1]]) * X.factorial(S[C[1]][C[0]]) % M;

  I res = 0;
  vector<I> T; // sizes of each connected component on the graph removing the centroid
  for(auto e: G[C[0]]) T.emplace_back(S[C[0]][e.to]);

  vector<vector<I>> dp(T.size() + 1, vector<I>(N + 1));
  dp[0][0] = 1;
  for(auto i = 0; i < T.size(); ++i) {
    for(I x = 0; x <= T[i]; ++x) {
      for(I k = 0; k + x <= N; ++k) {
        (dp[i + 1][k + x] += (dp[i][k] * X.combination(T[i], x) % M) * X.permutation(T[i], x) % M) %= M;
      }
    }
  }

  I sign = 1;
  for(I k = 0; k <= N; ++k) {
    (res += sign * X.factorial(N - k) * dp[T.size()][k] % M) %= M;
    (res += M) %= M;
    sign *= -1;
  }
  return res;
}

int main() {
  Size N;
  cin >> N;
  Graph G(N);
  for(auto i = 1; i < N; ++i) {
    Vertex x, y;
    cin >> x >> y; --x; --y;
    G[x].push_back({x, y});
    G[y].push_back({y, x});
  }
  cout << centroid(G) << endl;
}

```