// #include {{{
#include <iostream>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <complex>
#include <algorithm>
using namespace std;
// }}}
// #define {{{
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
// }}}

const int N = 5050 , P = 1e9 + 7;
inline void pp(int &x,int d) {if((x+=d)>=P)x-=P;}
int n , fac[N] , ifac[N];
vi g[N];
int sz[N] , mx[N];

int comb(int a,int b) {return ll(fac[a]) * ifac[b] % P * ifac[a-b] % P;}

void dfs(int c,int fa) {
  sz[c] = 1;
  mx[c] = 0;
  for(auto t : g[c]) if(t != fa) {
    dfs(t , c);
    mx[c] = max(mx[c] , sz[t]);
    sz[c] += sz[t];
  }
  mx[c] = max(mx[c] , n - sz[c]);
}

int main(){
  rep(i,0,N) fac[i] = i ? ll(fac[i-1]) * i % P : 1;
  rep(i,0,N) ifac[i] = i > 1 ? P - ll(P/i)*ifac[P%i]%P : 1;
  rep(i,1,N) ifac[i] = ll(ifac[i-1]) * ifac[i] % P;
  cin >> n;
  rep(i,1,n) {
    int x,y;
    cin >> x >> y;
    g[x].pb(y);
    g[y].pb(x);
  }
  dfs(1 , 0);
  vi centroid;
  rep(i,1,n+1) if(mx[i] <= n / 2)
    centroid.pb(i);
  if(sz(centroid) == 2) {
    cout << ll(fac[n / 2]) * fac[n / 2] % P << endl;
  } else {
    int rt = centroid[0];
    dfs(rt , 0);
    vi v , f(n , 0);
    f[0] = 1;
    for(auto t : g[rt]) {
      int sz = ::sz[t];
      vi g(n , 0);
      rep(i,0,n) if(f[i]) {
        rep(j,0,sz+1) {
          pp(g[i + j] , ll(f[i]) * comb(sz , j) % P * comb(sz , j) % P * fac[j] % P);
        }
      }
      swap(f , g);
    }
    int ans = 0;
    rep(i,0,n) {
      int cof = ll(f[i]) * fac[n - i] % P;
      if(i & 1) pp(ans , P - cof);
      else pp(ans , cof);
    }
    cout << ans << endl;
  }
  return 0;
}

### Prompt

In cpp, your task is to solve 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 {{{
#include <iostream>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <complex>
#include <algorithm>
using namespace std;
// }}}
// #define {{{
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
// }}}

const int N = 5050 , P = 1e9 + 7;
inline void pp(int &x,int d) {if((x+=d)>=P)x-=P;}
int n , fac[N] , ifac[N];
vi g[N];
int sz[N] , mx[N];

int comb(int a,int b) {return ll(fac[a]) * ifac[b] % P * ifac[a-b] % P;}

void dfs(int c,int fa) {
  sz[c] = 1;
  mx[c] = 0;
  for(auto t : g[c]) if(t != fa) {
    dfs(t , c);
    mx[c] = max(mx[c] , sz[t]);
    sz[c] += sz[t];
  }
  mx[c] = max(mx[c] , n - sz[c]);
}

int main(){
  rep(i,0,N) fac[i] = i ? ll(fac[i-1]) * i % P : 1;
  rep(i,0,N) ifac[i] = i > 1 ? P - ll(P/i)*ifac[P%i]%P : 1;
  rep(i,1,N) ifac[i] = ll(ifac[i-1]) * ifac[i] % P;
  cin >> n;
  rep(i,1,n) {
    int x,y;
    cin >> x >> y;
    g[x].pb(y);
    g[y].pb(x);
  }
  dfs(1 , 0);
  vi centroid;
  rep(i,1,n+1) if(mx[i] <= n / 2)
    centroid.pb(i);
  if(sz(centroid) == 2) {
    cout << ll(fac[n / 2]) * fac[n / 2] % P << endl;
  } else {
    int rt = centroid[0];
    dfs(rt , 0);
    vi v , f(n , 0);
    f[0] = 1;
    for(auto t : g[rt]) {
      int sz = ::sz[t];
      vi g(n , 0);
      rep(i,0,n) if(f[i]) {
        rep(j,0,sz+1) {
          pp(g[i + j] , ll(f[i]) * comb(sz , j) % P * comb(sz , j) % P * fac[j] % P);
        }
      }
      swap(f , g);
    }
    int ans = 0;
    rep(i,0,n) {
      int cof = ll(f[i]) * fac[n - i] % P;
      if(i & 1) pp(ans , P - cof);
      else pp(ans , cof);
    }
    cout << ans << endl;
  }
  return 0;
}

```