#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;

int N;
vector<int> G[5050];
int siz[5050];
vector<int> cent;

void solve(int v,int p){
  siz[v]=1;
  bool flag=1;
  for(int u:G[v]) if(u!=p){
    solve(u,v);
    if(siz[u]>N/2) flag=0;
    siz[v]+=siz[u];
  }
  if(N-siz[v]>N/2) flag=0;
  if(flag) cent.push_back(v);
}


const int MAX_N=5050;
ll inv[MAX_N+1], fact[MAX_N+1], ifact[MAX_N+1];

ll comb(int n, int k){
  if(n<k) return 0;
  return fact[n]*ifact[k]%MOD*ifact[n-k]%MOD;
}

void prepare(){
  inv[1]=fact[0]=fact[1]=ifact[0]=ifact[1]=1LL;
  for(int i=2;i<=MAX_N;i++){
    inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
    fact[i]=fact[i-1]*i%MOD;
    ifact[i]=ifact[i-1]*inv[i]%MOD;
  }
}


// dp[i][x]:i番目までにx個選んだ場合の選び方
ll to[5050], from[5050];

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  
  cin>>N;
  rep(i,N-1){
    int x,y; cin>>x>>y; x--,y--;
    G[x].push_back(y);
    G[y].push_back(x);
  }
  solve(0,-1);
  prepare();
  if(cent.size()==2){
    cout<<fact[N/2]*fact[N/2]%MOD<<endl;
    return 0;
  }
  from[0]=1;
  int c=cent[0], n=G[c].size();
  solve(c,-1);
  for(int v:G[c]){
    int s=siz[v];
    fill(to,to+5050,0);
    rep(j,N+1) if(from[j]){
      for(int k=0;k<=s;k++){
      (to[j+k]+=from[j]*comb(s,k)%MOD*comb(s,k)%MOD*fact[k])%=MOD;
      } 
    }
    swap(to,from);
  }
  ll ans=0;
  int sig=1;
  rep(i,N+1){
    (ans+=sig*fact[N-i]*from[i])%=MOD;
    ans=(ans+MOD)%MOD;
    sig*=-1;
  }
  cout<<ans<<endl;
  return 0;
}

### Prompt

Create a solution in Cpp for 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;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;

int N;
vector<int> G[5050];
int siz[5050];
vector<int> cent;

void solve(int v,int p){
  siz[v]=1;
  bool flag=1;
  for(int u:G[v]) if(u!=p){
    solve(u,v);
    if(siz[u]>N/2) flag=0;
    siz[v]+=siz[u];
  }
  if(N-siz[v]>N/2) flag=0;
  if(flag) cent.push_back(v);
}


const int MAX_N=5050;
ll inv[MAX_N+1], fact[MAX_N+1], ifact[MAX_N+1];

ll comb(int n, int k){
  if(n<k) return 0;
  return fact[n]*ifact[k]%MOD*ifact[n-k]%MOD;
}

void prepare(){
  inv[1]=fact[0]=fact[1]=ifact[0]=ifact[1]=1LL;
  for(int i=2;i<=MAX_N;i++){
    inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
    fact[i]=fact[i-1]*i%MOD;
    ifact[i]=ifact[i-1]*inv[i]%MOD;
  }
}


// dp[i][x]:i番目までにx個選んだ場合の選び方
ll to[5050], from[5050];

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  
  cin>>N;
  rep(i,N-1){
    int x,y; cin>>x>>y; x--,y--;
    G[x].push_back(y);
    G[y].push_back(x);
  }
  solve(0,-1);
  prepare();
  if(cent.size()==2){
    cout<<fact[N/2]*fact[N/2]%MOD<<endl;
    return 0;
  }
  from[0]=1;
  int c=cent[0], n=G[c].size();
  solve(c,-1);
  for(int v:G[c]){
    int s=siz[v];
    fill(to,to+5050,0);
    rep(j,N+1) if(from[j]){
      for(int k=0;k<=s;k++){
      (to[j+k]+=from[j]*comb(s,k)%MOD*comb(s,k)%MOD*fact[k])%=MOD;
      } 
    }
    swap(to,from);
  }
  ll ans=0;
  int sig=1;
  rep(i,N+1){
    (ans+=sig*fact[N-i]*from[i])%=MOD;
    ans=(ans+MOD)%MOD;
    sig*=-1;
  }
  cout<<ans<<endl;
  return 0;
}

```