#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>
#include <bitset>
#include <iomanip>

#define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n'
#define debugArrayP(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i].first<< " " << x[i].second << '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ll INF = LLONG_MAX;
const ll MOD = 1e9+7;

template <ll mod>
struct ModCombination{
    ll N;
    vector<ll> fact,inv,finv;

    ModCombination(ll n):N(n){
        fact.assign(n+1, 1);
        inv.assign(n+1, 1);
        finv.assign(n+1,1);
        for(int i=1;i<n;i++){
            fact[i+1] = fact[i]*(i+1)%mod;
            inv[i+1] = inv[mod%(i+1)]*(mod-mod/(i+1))%mod;
            finv[i+1] = finv[i]*inv[i+1]%mod;
        }
    }

    ll Comb(ll n,ll k){
        return (fact[n]*finv[k]%mod)*finv[n-k]%mod;
    }
};

struct CentroidGraph{
  int n;
  vector<vector<int>> g;
  vector<int> centroid;
  vector<int> size;
  CentroidGraph(int n_):n(n_),g(n_),size(n_){}
  void add_edge(int a,int b){
    g[a].push_back(b);
    g[b].push_back(a);
  }
  vector<int> findCentroid(){
          function<void (int, int)> dfs = [&](int u, int prev) {
                  size[u] = 1;
                  bool is_centroid = true;
                  for (auto v : g[u]) if (v != prev) {
                          dfs(v, u);
                          size[u] += size[v];
                          if (size[v] > n / 2) is_centroid = false;
                  }
                  if (n - size[u] > n / 2) is_centroid = false;
                  if (is_centroid) centroid.push_back(u);
          };
          dfs(0, -1);
          return centroid;
  }
  vector<int> operator[](const int& k){
    return g[k];
  }
};

ll dp[5010][5010];

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;cin>>N;
  ModCombination<MOD> C(N);
  CentroidGraph g(N);
  repeat(i,N-1){
    int x,y;cin>>x>>y;
    x--;y--;
    g.add_edge(x,y);
  }
  vint c = g.findCentroid();
  if(c.size()==2){
    cout << C.fact[N/2]*C.fact[N/2]%MOD << endl;
    return 0;
  }
  dp[0][0]=1;
  int K=0;
  for(int u:g[c[0]]){
    //debug(u);
    int size=g.size[u];
    if(size>N/2)size = N-g.size[c[0]];
    //debug(size);
    repeat(x,N+1){
      repeat(y,size+1){
        dp[K+1][x+y] = (dp[K+1][x+y]+dp[K][x]*C.Comb(size,y)%MOD*C.Comb(size,y)%MOD*C.fact[y]%MOD)%MOD;
      }
    }
    K++;
  }
  //debug(K);
  //debugArray(dp[K],N);
  ll ans = 0;
  repeat(x,N){
    ans = (ans+C.fact[N-x]*dp[K][x]%MOD*(1-2*(x&1))+MOD)%MOD;
  }
  cout << ans << endl;
  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 <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>
#include <bitset>
#include <iomanip>

#define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n'
#define debugArrayP(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i].first<< " " << x[i].second << '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ll INF = LLONG_MAX;
const ll MOD = 1e9+7;

template <ll mod>
struct ModCombination{
    ll N;
    vector<ll> fact,inv,finv;

    ModCombination(ll n):N(n){
        fact.assign(n+1, 1);
        inv.assign(n+1, 1);
        finv.assign(n+1,1);
        for(int i=1;i<n;i++){
            fact[i+1] = fact[i]*(i+1)%mod;
            inv[i+1] = inv[mod%(i+1)]*(mod-mod/(i+1))%mod;
            finv[i+1] = finv[i]*inv[i+1]%mod;
        }
    }

    ll Comb(ll n,ll k){
        return (fact[n]*finv[k]%mod)*finv[n-k]%mod;
    }
};

struct CentroidGraph{
  int n;
  vector<vector<int>> g;
  vector<int> centroid;
  vector<int> size;
  CentroidGraph(int n_):n(n_),g(n_),size(n_){}
  void add_edge(int a,int b){
    g[a].push_back(b);
    g[b].push_back(a);
  }
  vector<int> findCentroid(){
          function<void (int, int)> dfs = [&](int u, int prev) {
                  size[u] = 1;
                  bool is_centroid = true;
                  for (auto v : g[u]) if (v != prev) {
                          dfs(v, u);
                          size[u] += size[v];
                          if (size[v] > n / 2) is_centroid = false;
                  }
                  if (n - size[u] > n / 2) is_centroid = false;
                  if (is_centroid) centroid.push_back(u);
          };
          dfs(0, -1);
          return centroid;
  }
  vector<int> operator[](const int& k){
    return g[k];
  }
};

ll dp[5010][5010];

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;cin>>N;
  ModCombination<MOD> C(N);
  CentroidGraph g(N);
  repeat(i,N-1){
    int x,y;cin>>x>>y;
    x--;y--;
    g.add_edge(x,y);
  }
  vint c = g.findCentroid();
  if(c.size()==2){
    cout << C.fact[N/2]*C.fact[N/2]%MOD << endl;
    return 0;
  }
  dp[0][0]=1;
  int K=0;
  for(int u:g[c[0]]){
    //debug(u);
    int size=g.size[u];
    if(size>N/2)size = N-g.size[c[0]];
    //debug(size);
    repeat(x,N+1){
      repeat(y,size+1){
        dp[K+1][x+y] = (dp[K+1][x+y]+dp[K][x]*C.Comb(size,y)%MOD*C.Comb(size,y)%MOD*C.fact[y]%MOD)%MOD;
      }
    }
    K++;
  }
  //debug(K);
  //debugArray(dp[K],N);
  ll ans = 0;
  repeat(x,N){
    ans = (ans+C.fact[N-x]*dp[K][x]%MOD*(1-2*(x&1))+MOD)%MOD;
  }
  cout << ans << endl;
  return 0;
}

```