#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN=5000;
const int MOD=1000000007;

int n;
vector<int> adj[MAXN];

int sz[MAXN];

int dfscentroid(int at,int par) {
	sz[at]=1;
	int cmx=0;
	REPSZ(i,adj[at]) {
		int to=adj[at][i]; if(to==par) continue;
		int ret=dfscentroid(to,at); if(ret!=-1) return ret;
		sz[at]+=sz[to]; cmx=max(cmx,sz[to]);
	}
	cmx=max(cmx,n-sz[at]);
	return 2*cmx<=n?at:-1;
}

int centroid(int at) {
	return dfscentroid(at,-1);
}

int dfssz(int at,int par) {
	int ret=1;
	REPSZ(i,adj[at]) { int to=adj[at][i]; if(to==par) continue; ret+=dfssz(to,at); }
	return ret;
}

int a[MAXN],na;

int fac[MAXN+1];
int C[MAXN+1][MAXN+1];
int dp[MAXN+1][MAXN+1]; // dp[i][j] = # ways to fix j items out of the first i groups within its own group

int calc(int na) {
	//printf("a:"); REP(i,na) printf(" %d",a[i]); puts("");
	int cnt=0; REP(i,na) cnt+=a[i];
	memset(dp,0,sizeof(dp)); dp[0][0]=1; int sofar=0;
	REP(i,na) {
		REPE(j,sofar) REPE(k,a[i]) {
			dp[i+1][j+k]=(dp[i+1][j+k]+(ll)dp[i][j]*C[a[i]][k]%MOD*C[a[i]][k]%MOD*fac[k])%MOD;
		}
		sofar+=a[i];
	}
	//REPE(j,sofar) printf("%d: %d\n",j,dp[na][j]);

	int ret=0;
	REPE(j,sofar) {
		int cur=(ll)dp[na][j]*fac[cnt-j]%MOD;
		if(j%2==0) ret=(ret+cur)%MOD; else ret=(ret+MOD-cur)%MOD;
	}
	return ret;
}

void run() {
	fac[0]=1; FORE(i,1,MAXN) fac[i]=(ll)fac[i-1]*i%MOD;
	REPE(i,MAXN) { C[i][0]=C[i][i]=1; FOR(j,1,i) C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD; }

	scanf("%d",&n); REP(i,n-1) { int a,b; scanf("%d%d",&a,&b); --a,--b; adj[a].PB(b); adj[b].PB(a); }
	
	int c=centroid(0);
	na=0; REPSZ(i,adj[c]) a[na++]=dfssz(adj[c][i],c); a[na++]=1;
	

	int ret=(calc(na)+calc(na-1))%MOD;
	printf("%d\n",ret);
}

int main() {
	run();
	return 0;
}

### Prompt

Your challenge is to write 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 <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN=5000;
const int MOD=1000000007;

int n;
vector<int> adj[MAXN];

int sz[MAXN];

int dfscentroid(int at,int par) {
	sz[at]=1;
	int cmx=0;
	REPSZ(i,adj[at]) {
		int to=adj[at][i]; if(to==par) continue;
		int ret=dfscentroid(to,at); if(ret!=-1) return ret;
		sz[at]+=sz[to]; cmx=max(cmx,sz[to]);
	}
	cmx=max(cmx,n-sz[at]);
	return 2*cmx<=n?at:-1;
}

int centroid(int at) {
	return dfscentroid(at,-1);
}

int dfssz(int at,int par) {
	int ret=1;
	REPSZ(i,adj[at]) { int to=adj[at][i]; if(to==par) continue; ret+=dfssz(to,at); }
	return ret;
}

int a[MAXN],na;

int fac[MAXN+1];
int C[MAXN+1][MAXN+1];
int dp[MAXN+1][MAXN+1]; // dp[i][j] = # ways to fix j items out of the first i groups within its own group

int calc(int na) {
	//printf("a:"); REP(i,na) printf(" %d",a[i]); puts("");
	int cnt=0; REP(i,na) cnt+=a[i];
	memset(dp,0,sizeof(dp)); dp[0][0]=1; int sofar=0;
	REP(i,na) {
		REPE(j,sofar) REPE(k,a[i]) {
			dp[i+1][j+k]=(dp[i+1][j+k]+(ll)dp[i][j]*C[a[i]][k]%MOD*C[a[i]][k]%MOD*fac[k])%MOD;
		}
		sofar+=a[i];
	}
	//REPE(j,sofar) printf("%d: %d\n",j,dp[na][j]);

	int ret=0;
	REPE(j,sofar) {
		int cur=(ll)dp[na][j]*fac[cnt-j]%MOD;
		if(j%2==0) ret=(ret+cur)%MOD; else ret=(ret+MOD-cur)%MOD;
	}
	return ret;
}

void run() {
	fac[0]=1; FORE(i,1,MAXN) fac[i]=(ll)fac[i-1]*i%MOD;
	REPE(i,MAXN) { C[i][0]=C[i][i]=1; FOR(j,1,i) C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD; }

	scanf("%d",&n); REP(i,n-1) { int a,b; scanf("%d%d",&a,&b); --a,--b; adj[a].PB(b); adj[b].PB(a); }
	
	int c=centroid(0);
	na=0; REPSZ(i,adj[c]) a[na++]=dfssz(adj[c][i],c); a[na++]=1;
	

	int ret=(calc(na)+calc(na-1))%MOD;
	printf("%d\n",ret);
}

int main() {
	run();
	return 0;
}

```