#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

typedef long long cat;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

void DFS(int R, vector< vector<int> > &G, vector<int> &S, vector<int> &par) {
	S[R] =1;
	ALL_THE(G[R],it) if(S[*it] == 0) {
		DFS(*it,G,S,par);
		par[*it] =R;
		S[R] +=S[*it];
	}
}

cat pw(cat a, cat e, cat mod) {
	if(e <= 0) return 1;
	cat x =pw(a,e/2,mod);
	x =(x*x)%mod;
	if(e%2) x =(x*a)%mod;
	return x;
}

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int N;
	cin >> N;
	vector< vector<int> > G(N);
	for(int i =0; i < N-1; i++) {
		int x,y;
		cin >> x >> y;
		G[--x].push_back(--y);
		G[y].push_back(x);
	}

	vector<int> S(N,0), par(N,0);
	DFS(0,G,S,par);
	int c =0;
	for(int i =0; i < N; i++) {
		bool isc =(S[i] >= N-S[i]);
		ALL_THE(G[i],it) if(*it != par[i] && S[*it] > N-S[*it]) isc =false;
		if(isc) c =i;
	}
	for(int i =0; i < N; i++) S[i] =0;
	par[c] =c;
	DFS(c,G,S,par);
	vector<int> A;
	ALL_THE(G[c],it) A.push_back(S[*it]);
	A.push_back(1);
	int M =A.size();

	cat mod =1000000007;
	vector<cat> fac(10000,1), inv(10000,1);
	for(int i =1; i < 10000; i++) fac[i] =(i*fac[i-1])%mod;
	for(int i =1; i < 10000; i++) inv[i] =pw(fac[i],mod-2,mod);
	vector< vector<cat> > cnt(M+1,vector<cat>(N+1,0));
	cnt[0][0] =1;
	for(int i =0; i < M; i++) for(int k =0; k <= A[i]; k++) {
		cat C =(fac[A[i]]*inv[k])%mod*inv[A[i]-k]%mod;
		C =C*fac[A[i]]%mod*inv[A[i]-k]%mod;
		for(int j =0; j <= N-k; j++)
			cnt[i+1][j+k] =(cnt[i+1][j+k]+cnt[i][j]*C)%mod;
	}
	
	cat ans =0;
	for(int i =N; i >= 0; i--) {
		if((N-i)%2) ans =(ans-fac[i]*cnt[M][N-i])%mod;
		else ans =(ans+fac[i]*cnt[M][N-i])%mod;
	}
	for(int i =N-1; i >= 0; i--) {
		if((N-1-i)%2) ans =(ans-fac[i]*cnt[M-1][N-1-i])%mod;
		else ans =(ans+fac[i]*cnt[M-1][N-1-i])%mod;
	}
	ans %=mod;
	if(ans < 0) ans +=mod;
	cout << ans << "\n";
	return 0;
}

// look at my code
// my code is amazing

### 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>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

typedef long long cat;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

void DFS(int R, vector< vector<int> > &G, vector<int> &S, vector<int> &par) {
	S[R] =1;
	ALL_THE(G[R],it) if(S[*it] == 0) {
		DFS(*it,G,S,par);
		par[*it] =R;
		S[R] +=S[*it];
	}
}

cat pw(cat a, cat e, cat mod) {
	if(e <= 0) return 1;
	cat x =pw(a,e/2,mod);
	x =(x*x)%mod;
	if(e%2) x =(x*a)%mod;
	return x;
}

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int N;
	cin >> N;
	vector< vector<int> > G(N);
	for(int i =0; i < N-1; i++) {
		int x,y;
		cin >> x >> y;
		G[--x].push_back(--y);
		G[y].push_back(x);
	}

	vector<int> S(N,0), par(N,0);
	DFS(0,G,S,par);
	int c =0;
	for(int i =0; i < N; i++) {
		bool isc =(S[i] >= N-S[i]);
		ALL_THE(G[i],it) if(*it != par[i] && S[*it] > N-S[*it]) isc =false;
		if(isc) c =i;
	}
	for(int i =0; i < N; i++) S[i] =0;
	par[c] =c;
	DFS(c,G,S,par);
	vector<int> A;
	ALL_THE(G[c],it) A.push_back(S[*it]);
	A.push_back(1);
	int M =A.size();

	cat mod =1000000007;
	vector<cat> fac(10000,1), inv(10000,1);
	for(int i =1; i < 10000; i++) fac[i] =(i*fac[i-1])%mod;
	for(int i =1; i < 10000; i++) inv[i] =pw(fac[i],mod-2,mod);
	vector< vector<cat> > cnt(M+1,vector<cat>(N+1,0));
	cnt[0][0] =1;
	for(int i =0; i < M; i++) for(int k =0; k <= A[i]; k++) {
		cat C =(fac[A[i]]*inv[k])%mod*inv[A[i]-k]%mod;
		C =C*fac[A[i]]%mod*inv[A[i]-k]%mod;
		for(int j =0; j <= N-k; j++)
			cnt[i+1][j+k] =(cnt[i+1][j+k]+cnt[i][j]*C)%mod;
	}
	
	cat ans =0;
	for(int i =N; i >= 0; i--) {
		if((N-i)%2) ans =(ans-fac[i]*cnt[M][N-i])%mod;
		else ans =(ans+fac[i]*cnt[M][N-i])%mod;
	}
	for(int i =N-1; i >= 0; i--) {
		if((N-1-i)%2) ans =(ans-fac[i]*cnt[M-1][N-1-i])%mod;
		else ans =(ans+fac[i]*cnt[M-1][N-1-i])%mod;
	}
	ans %=mod;
	if(ans < 0) ans +=mod;
	cout << ans << "\n";
	return 0;
}

// look at my code
// my code is amazing

```