#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
/*#### modular_arithmetic */
class modular_arithmetic{
public:
	int mod, range;

	modular_arithmetic(){
		mod = 1000000007;
	}
	//No specific settings.
	void set_mod(int _mod){mod = _mod;}
	int add(int x,int y){return (x+y)%mod;}
	int sub(int x,int y){return (x-y+mod)%mod;}
	int mul(int x,int y){return (int)((long long int)x*y%mod);}
	int pw(int x,int y){
		int r = 1;
		while(1){
			if(y&1)r=mul(r,x);
			if(y>>=1)x=mul(x,x);else
				break;
		}
		return r;
	}
};
/*####*/

modular_arithmetic ma;

int n;bool ff;
vector<int> e[5005];
int sz[5005];

int m,a[5005];
void dfs(int x,int fat){
	sz[x] = 1;
	int mx = 0;
	for(vector<int>::iterator it = e[x].begin(); it != e[x].end(); it++){
		int y = *it;
		if(y == fat)continue;
		dfs(y, x);
		sz[x] += sz[y];
		if(sz[y] + sz[y] == n){
			ff = true;
		}
		mx = max(mx, sz[y]);
	}
	mx = max(mx, n - sz[x]);
	if(mx + mx < n){
		a[m++] = n-sz[x];
		for(vector<int>::iterator it = e[x].begin(); it != e[x].end(); it++){
			int y = *it;
			if(y == fat)continue;
			a[m++] = sz[y];
		}
	}
}

int fac[5005],ifac[5005];
void init(){
	fac[0] = 1;
	for(int i=1; i<=n; i++)
		fac[i] = ma.mul(fac[i-1],i);
	ifac[n] = ma.pw(fac[n],ma.mod-2);
	for(int i=n; i>=1; i--)
		ifac[i-1] = ma.mul(ifac[i], i);
}

int d[5005],d2[5005];
int solve(){
	memset(d,0,sizeof(d));
	d[0] = 1;
	int N = 0;
	sort(a,a+m);
	for(int i=0; i<m; i++){
		memset(d2,0,sizeof(d2));
		for(int j=0; j<=N; j++)if(d[j])
			for(int k=0; k<=a[i]; k++){
				int W = ma.mul(fac[a[i]], ifac[a[i]-k]);
				W = ma.mul(W, W);
				W = ma.mul(W, ifac[k]);
				d2[j+k] = ma.add(d2[j+k], ma.mul(d[j], W));
			}
		memcpy(d,d2,sizeof(d2));
		N += a[i];
	}

	int res = 0;
	for(int i=0; i<=N; i++){
		int cur = ma.mul(d[i], fac[N-i]);
		if(i%2)res = ma.sub(res, cur);else
			res = ma.add(res, cur);
	}
	return res;
}


int solve_1(){
	init();
	int ret = solve();
	a[m++] = 1;
	return ma.add(ret, solve());
}

int main(){
	scanf("%d",&n);
	for(int i=1; i<n; i++){
		int x,y;
		scanf("%d%d",&x,&y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	ff = false;
	dfs(1,1);
	if(ff){
		int res = 1;
		for(int i=1; i+i<=n; i++)
			res = ma.mul(res, i);
		res = ma.mul(res, res);
		printf("%d\n",res);
	}else{
		printf("%d\n",solve_1());
	}
	return 0;
}

### Prompt

Please formulate 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<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
/*#### modular_arithmetic */
class modular_arithmetic{
public:
	int mod, range;

	modular_arithmetic(){
		mod = 1000000007;
	}
	//No specific settings.
	void set_mod(int _mod){mod = _mod;}
	int add(int x,int y){return (x+y)%mod;}
	int sub(int x,int y){return (x-y+mod)%mod;}
	int mul(int x,int y){return (int)((long long int)x*y%mod);}
	int pw(int x,int y){
		int r = 1;
		while(1){
			if(y&1)r=mul(r,x);
			if(y>>=1)x=mul(x,x);else
				break;
		}
		return r;
	}
};
/*####*/

modular_arithmetic ma;

int n;bool ff;
vector<int> e[5005];
int sz[5005];

int m,a[5005];
void dfs(int x,int fat){
	sz[x] = 1;
	int mx = 0;
	for(vector<int>::iterator it = e[x].begin(); it != e[x].end(); it++){
		int y = *it;
		if(y == fat)continue;
		dfs(y, x);
		sz[x] += sz[y];
		if(sz[y] + sz[y] == n){
			ff = true;
		}
		mx = max(mx, sz[y]);
	}
	mx = max(mx, n - sz[x]);
	if(mx + mx < n){
		a[m++] = n-sz[x];
		for(vector<int>::iterator it = e[x].begin(); it != e[x].end(); it++){
			int y = *it;
			if(y == fat)continue;
			a[m++] = sz[y];
		}
	}
}

int fac[5005],ifac[5005];
void init(){
	fac[0] = 1;
	for(int i=1; i<=n; i++)
		fac[i] = ma.mul(fac[i-1],i);
	ifac[n] = ma.pw(fac[n],ma.mod-2);
	for(int i=n; i>=1; i--)
		ifac[i-1] = ma.mul(ifac[i], i);
}

int d[5005],d2[5005];
int solve(){
	memset(d,0,sizeof(d));
	d[0] = 1;
	int N = 0;
	sort(a,a+m);
	for(int i=0; i<m; i++){
		memset(d2,0,sizeof(d2));
		for(int j=0; j<=N; j++)if(d[j])
			for(int k=0; k<=a[i]; k++){
				int W = ma.mul(fac[a[i]], ifac[a[i]-k]);
				W = ma.mul(W, W);
				W = ma.mul(W, ifac[k]);
				d2[j+k] = ma.add(d2[j+k], ma.mul(d[j], W));
			}
		memcpy(d,d2,sizeof(d2));
		N += a[i];
	}

	int res = 0;
	for(int i=0; i<=N; i++){
		int cur = ma.mul(d[i], fac[N-i]);
		if(i%2)res = ma.sub(res, cur);else
			res = ma.add(res, cur);
	}
	return res;
}


int solve_1(){
	init();
	int ret = solve();
	a[m++] = 1;
	return ma.add(ret, solve());
}

int main(){
	scanf("%d",&n);
	for(int i=1; i<n; i++){
		int x,y;
		scanf("%d%d",&x,&y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	ff = false;
	dfs(1,1);
	if(ff){
		int res = 1;
		for(int i=1; i+i<=n; i++)
			res = ma.mul(res, i);
		res = ma.mul(res, res);
		printf("%d\n",res);
	}else{
		printf("%d\n",solve_1());
	}
	return 0;
}

```