#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
inline int mul(int x, int y) { return (1LL*x*y)%MOD; }
inline void add(int &x, int v) { x += v; if (x >= MOD) x -= MOD; }


int N;
int sz[5000], mc[5000];
vector<int> G[5000];
int fact[5001];
int nCr[5001][5001];

void dfs2(int x, int p) {
  sz[x] = 1;
  for (int t : G[x]) if (t != p) dfs2(t, x), sz[x] += sz[t], mc[x] = max(mc[x], sz[t]);
  mc[x] = max(mc[x], N-sz[x]);
}

int dp[5001][5001];
int solve(vector<int> seq) {
  //cout<<"{";for (int x : seq) cout << x<<",";cout<<"}\n";
  int n = seq.size(), sum = 0;
  for (int x : seq) sum += x;
  rep(i, n+1) rep(j, sum+1) dp[i][j] = 0;
  dp[0][0] = 1;
  rep(i, n) {
    int a = seq[i];
    rep(j, sum-a+1) {
      rep(c, a+1) add(dp[i+1][j+c], mul(dp[i][j], mul(mul(nCr[a][c], nCr[a][c]), fact[c])));
    }
  }
  int s = 0;
  rep(i, sum+1) {
    int w = mul(dp[n][i], fact[sum-i]);
    if (i%2) w = MOD-w;
    add(s, w);
  }
  return s;
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  nCr[0][0] = 1;
  for (int i=1; i<=5000; i++) {
    nCr[i][0] = 1;
    for (int j=1; j<=5000; j++) nCr[i][j] = (nCr[i-1][j-1]+nCr[i-1][j]) % MOD;
  }
  fact[0] = 1;
  for (int i=1; i<=5000; i++) fact[i] = (1LL*i*fact[i-1]) % MOD;
  cin >> N;
  rep(i, N-1) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    G[u].pb(v);
    G[v].pb(u);
  }
  dfs2(0, -1);
  vector<P> ps;
  rep(i, N) ps.pb(P(mc[i], i));
  sort(all(ps));
  int s = 0;
  if (ps[0]._1==ps[1]._1) {
    s = solve({N/2, N/2});
  }
  else {
    vector<int> seq;
    int g = ps[0]._2;
    for (int t : G[g]) {
      dfs2(t, g);
      seq.pb(sz[t]);
    }
    s = solve(seq);
    seq.pb(1);
    add(s, solve(seq));
  }
  cout << s << "\n";
  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 <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
inline int mul(int x, int y) { return (1LL*x*y)%MOD; }
inline void add(int &x, int v) { x += v; if (x >= MOD) x -= MOD; }


int N;
int sz[5000], mc[5000];
vector<int> G[5000];
int fact[5001];
int nCr[5001][5001];

void dfs2(int x, int p) {
  sz[x] = 1;
  for (int t : G[x]) if (t != p) dfs2(t, x), sz[x] += sz[t], mc[x] = max(mc[x], sz[t]);
  mc[x] = max(mc[x], N-sz[x]);
}

int dp[5001][5001];
int solve(vector<int> seq) {
  //cout<<"{";for (int x : seq) cout << x<<",";cout<<"}\n";
  int n = seq.size(), sum = 0;
  for (int x : seq) sum += x;
  rep(i, n+1) rep(j, sum+1) dp[i][j] = 0;
  dp[0][0] = 1;
  rep(i, n) {
    int a = seq[i];
    rep(j, sum-a+1) {
      rep(c, a+1) add(dp[i+1][j+c], mul(dp[i][j], mul(mul(nCr[a][c], nCr[a][c]), fact[c])));
    }
  }
  int s = 0;
  rep(i, sum+1) {
    int w = mul(dp[n][i], fact[sum-i]);
    if (i%2) w = MOD-w;
    add(s, w);
  }
  return s;
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  nCr[0][0] = 1;
  for (int i=1; i<=5000; i++) {
    nCr[i][0] = 1;
    for (int j=1; j<=5000; j++) nCr[i][j] = (nCr[i-1][j-1]+nCr[i-1][j]) % MOD;
  }
  fact[0] = 1;
  for (int i=1; i<=5000; i++) fact[i] = (1LL*i*fact[i-1]) % MOD;
  cin >> N;
  rep(i, N-1) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    G[u].pb(v);
    G[v].pb(u);
  }
  dfs2(0, -1);
  vector<P> ps;
  rep(i, N) ps.pb(P(mc[i], i));
  sort(all(ps));
  int s = 0;
  if (ps[0]._1==ps[1]._1) {
    s = solve({N/2, N/2});
  }
  else {
    vector<int> seq;
    int g = ps[0]._2;
    for (int t : G[g]) {
      dfs2(t, g);
      seq.pb(sz[t]);
    }
    s = solve(seq);
    seq.pb(1);
    add(s, solve(seq));
  }
  cout << s << "\n";
  return 0;
}

```