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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF INT_MAX/3
#define mod 1000000007

ll mod_pow(ll a,ll n){
  ll res=1;
  while(n>0){
    if(n&1)res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

int sz[5001];
int n;
vector<int> g[5001];
ll dp[2][5001];
vector<int> cs;
ll fac[5001],finv[5001];
vector<int> a;

ll comb(ll a,ll b){
  if(a<0||b<0||a<b)return 0;
  else return  (fac[a]*finv[b]%mod)*finv[a-b]%mod;
}

void dfs(int v,int pre){
  sz[v]=1;
  bool is_cent=true;
  for(int nv : g[v]){
    if(nv==pre)continue;
    dfs(nv,v);
    if(sz[nv]>n/2)is_cent=false;
    sz[v]+=sz[nv];
  }
  if(n-sz[v]>n/2)is_cent=false;
  if(is_cent)cs.push_back(v);
}

int main(){
  fac[0]=1;
  rep(i,5000)fac[i+1]=fac[i]*(i+1)%mod;
  rep(i,5001)finv[i]=mod_pow(fac[i],mod-2);

  cin>>n;
  rep(i,n-1){
    int a,b;
    cin>>a>>b;
    a--;b--;
    g[a].push_back(b);
    g[b].push_back(a);    
  }
  dfs(0,-1);
  if(cs.size()==2){
    cout<<fac[n/2]*fac[n/2]%mod<<endl;
    return 0;
  }else{
    int r=cs[0];
    for(int v : g[r]){
      if(sz[v]>sz[r])continue;
      a.push_back(sz[v]);
    }
    if(n-sz[r]>0)a.push_back(n-sz[r]);
    int crt=0,nxt=1;
    dp[crt][0]=1;
    rep(i,a.size()){
      memset(dp[nxt],0,sizeof(dp[nxt]));
      rep(j,n){
        rep(k,a[i]+1){
          if(j+k>n-1)continue;
          ll c2=comb(a[i],k)*comb(a[i],k)%mod;
          (dp[nxt][j+k]+=(dp[crt][j]*c2%mod)*fac[k]%mod)%=mod;
        }
      }
      swap(crt,nxt);
    }
    ll res=0;
    rep(x,n){
      ll sgn=(x%2==0?+1:-1);
      (res+=(sgn*((dp[crt][x]*fac[n-x])%mod)+mod)%mod)%=mod;
    }
    cout<<res<<endl;
  }
  return 0;
}

### Prompt

Generate 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 <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF INT_MAX/3
#define mod 1000000007

ll mod_pow(ll a,ll n){
  ll res=1;
  while(n>0){
    if(n&1)res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

int sz[5001];
int n;
vector<int> g[5001];
ll dp[2][5001];
vector<int> cs;
ll fac[5001],finv[5001];
vector<int> a;

ll comb(ll a,ll b){
  if(a<0||b<0||a<b)return 0;
  else return  (fac[a]*finv[b]%mod)*finv[a-b]%mod;
}

void dfs(int v,int pre){
  sz[v]=1;
  bool is_cent=true;
  for(int nv : g[v]){
    if(nv==pre)continue;
    dfs(nv,v);
    if(sz[nv]>n/2)is_cent=false;
    sz[v]+=sz[nv];
  }
  if(n-sz[v]>n/2)is_cent=false;
  if(is_cent)cs.push_back(v);
}

int main(){
  fac[0]=1;
  rep(i,5000)fac[i+1]=fac[i]*(i+1)%mod;
  rep(i,5001)finv[i]=mod_pow(fac[i],mod-2);

  cin>>n;
  rep(i,n-1){
    int a,b;
    cin>>a>>b;
    a--;b--;
    g[a].push_back(b);
    g[b].push_back(a);    
  }
  dfs(0,-1);
  if(cs.size()==2){
    cout<<fac[n/2]*fac[n/2]%mod<<endl;
    return 0;
  }else{
    int r=cs[0];
    for(int v : g[r]){
      if(sz[v]>sz[r])continue;
      a.push_back(sz[v]);
    }
    if(n-sz[r]>0)a.push_back(n-sz[r]);
    int crt=0,nxt=1;
    dp[crt][0]=1;
    rep(i,a.size()){
      memset(dp[nxt],0,sizeof(dp[nxt]));
      rep(j,n){
        rep(k,a[i]+1){
          if(j+k>n-1)continue;
          ll c2=comb(a[i],k)*comb(a[i],k)%mod;
          (dp[nxt][j+k]+=(dp[crt][j]*c2%mod)*fac[k]%mod)%=mod;
        }
      }
      swap(crt,nxt);
    }
    ll res=0;
    rep(x,n){
      ll sgn=(x%2==0?+1:-1);
      (res+=(sgn*((dp[crt][x]*fac[n-x])%mod)+mod)%mod)%=mod;
    }
    cout<<res<<endl;
  }
  return 0;
}

```