#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl
#define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl
#define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl
#define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 5005;

class centroid
{
public:
	int V;
	vector<vector<int> > G;
	vector<int> sz;
    centroid(int node_size) : V(node_size), G(V), sz(V, 0){}
    void add_edge(int u,int v){
        G[u].push_back(v),G[v].push_back(u);
    }
    void dfs(int u,int p, vector<int>& ct){
		bool ok = true;
        sz[u] = 1;
        for(int v : G[u]){
            if(v != p){
                dfs(v, u, ct);
                sz[u] += sz[v];
				if(2*sz[v] > V) ok = false;
            }
        }
		if(ok && V <= 2*sz[u]) ct.push_back(u);
    }
    vector<int> solve(){
		vector<int> ct;
        dfs(0, -1, ct);
		return ct;
    }
};

inline int mod_pow(int a, ll b)
{
    int res = 1;
    while(b){
        if(b & 1){
            res = (ll)res * a % MOD;
        }
        a = (ll)a * a % MOD;
        b >>= 1;
    }
    return res;
}

inline int add(int x,int y)
{
    return (x + y)%MOD;
}

inline int sub(int x,int y)
{
    return (x+MOD-y)%MOD;
}

inline int mul(int x,int y)
{
    return (ll)x*y%MOD;
}

int inv[MAX_N],fac[MAX_N],finv[MAX_N];

void make()
{
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for(int i=2;i<MAX_N;i++){
		inv[i] = MOD - (ll)inv[MOD%i] * (MOD/i) % MOD;
		fac[i] = (ll)fac[i-1] * i % MOD;
		finv[i] = (ll)finv[i-1] * inv[i] % MOD;
	}
}

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

int redfs(int u, int p, vvi& G)
{
	int res = 1;
	each(v,G[u]){
		if(v != p){
			res += redfs(v, u, G);
		}
	}
	return res;
}

int dp[MAX_N][MAX_N];

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
	centroid ct(n);
	rep(i,n-1){
		int a,b;
		cin >> a >> b;
		ct.add_edge(a-1,b-1);
	}
	auto res = ct.solve();
	make();
	if(len(res) == 2){
		cout << mul(fac[n/2],fac[n/2]) << "\n";
		return 0;
	}
	int u = res[0];
	int K = len(ct.G[u]);
	vi cnt(K);
	rep(i,K){
		cnt[i] = redfs(ct.G[u][i], u, ct.G);
	}
	dp[0][0] = 1;
	int mx = 0;
	rep(i,K){
		rep(j,mx+1){
			rep(k,cnt[i]+1){
				dp[i+1][j+k] = add(dp[i+1][j+k],mul(dp[i][j],mul(mod_pow(comb(cnt[i],k),2),fac[k])));
			}
		}
		mx += cnt[i];
	}
	int ans = 0;
	rep(i,n){
		if(i % 2){
			ans = sub(ans, mul(fac[n-i],dp[K][i]));
		}else{
			ans = add(ans, mul(fac[n-i],dp[K][i]));
		}
	}
	cout << ans << "\n";
    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>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl
#define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl
#define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl
#define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 5005;

class centroid
{
public:
	int V;
	vector<vector<int> > G;
	vector<int> sz;
    centroid(int node_size) : V(node_size), G(V), sz(V, 0){}
    void add_edge(int u,int v){
        G[u].push_back(v),G[v].push_back(u);
    }
    void dfs(int u,int p, vector<int>& ct){
		bool ok = true;
        sz[u] = 1;
        for(int v : G[u]){
            if(v != p){
                dfs(v, u, ct);
                sz[u] += sz[v];
				if(2*sz[v] > V) ok = false;
            }
        }
		if(ok && V <= 2*sz[u]) ct.push_back(u);
    }
    vector<int> solve(){
		vector<int> ct;
        dfs(0, -1, ct);
		return ct;
    }
};

inline int mod_pow(int a, ll b)
{
    int res = 1;
    while(b){
        if(b & 1){
            res = (ll)res * a % MOD;
        }
        a = (ll)a * a % MOD;
        b >>= 1;
    }
    return res;
}

inline int add(int x,int y)
{
    return (x + y)%MOD;
}

inline int sub(int x,int y)
{
    return (x+MOD-y)%MOD;
}

inline int mul(int x,int y)
{
    return (ll)x*y%MOD;
}

int inv[MAX_N],fac[MAX_N],finv[MAX_N];

void make()
{
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for(int i=2;i<MAX_N;i++){
		inv[i] = MOD - (ll)inv[MOD%i] * (MOD/i) % MOD;
		fac[i] = (ll)fac[i-1] * i % MOD;
		finv[i] = (ll)finv[i-1] * inv[i] % MOD;
	}
}

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

int redfs(int u, int p, vvi& G)
{
	int res = 1;
	each(v,G[u]){
		if(v != p){
			res += redfs(v, u, G);
		}
	}
	return res;
}

int dp[MAX_N][MAX_N];

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
	centroid ct(n);
	rep(i,n-1){
		int a,b;
		cin >> a >> b;
		ct.add_edge(a-1,b-1);
	}
	auto res = ct.solve();
	make();
	if(len(res) == 2){
		cout << mul(fac[n/2],fac[n/2]) << "\n";
		return 0;
	}
	int u = res[0];
	int K = len(ct.G[u]);
	vi cnt(K);
	rep(i,K){
		cnt[i] = redfs(ct.G[u][i], u, ct.G);
	}
	dp[0][0] = 1;
	int mx = 0;
	rep(i,K){
		rep(j,mx+1){
			rep(k,cnt[i]+1){
				dp[i+1][j+k] = add(dp[i+1][j+k],mul(dp[i][j],mul(mod_pow(comb(cnt[i],k),2),fac[k])));
			}
		}
		mx += cnt[i];
	}
	int ans = 0;
	rep(i,n){
		if(i % 2){
			ans = sub(ans, mul(fac[n-i],dp[K][i]));
		}else{
			ans = add(ans, mul(fac[n-i],dp[K][i]));
		}
	}
	cout << ans << "\n";
    return 0;
}

```