#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#define MOD 1000000007LL

using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

long long int powmod(long long int a, long long int k, long long int m){ //0<=a<=1e9, 0<k<=1e9+9, 0<m<=1e9+9
	if(a==0){
		return 0;
	}
	long long int apow[30];
	apow[0]=a;
	for(int i=1; i<30; i++){
		apow[i]=apow[i-1]*apow[i-1]%m;
	}
	long long int ans=1;
	for(int i=29; i>=0; i--){
		if(k>=(1ll<<i)){
			ans=ans*apow[i]%m;
			k-=(1ll<<i);
		}
	}
	return ans;
}
 
ll inv(ll x, ll p){
  return powmod(x, p-2, p);
}

ll f[5001], invf[5001];
void factorial(){
	f[0]=1;
	for(ll i=1; i<=5000; i++){
		f[i]=f[i-1]*i%MOD;
	}
	invf[5000]=inv(f[5000], MOD);
	for(ll i=4999; i>=0; i--){
		invf[i]=invf[i+1]*(i+1)%MOD;
	}
}

vector<ll> polymul(vector<ll> f, vector<ll> g){
	int m=f.size(), n=g.size();
	vector<ll> h;
	for(int k=0; k<m+n-1; k++){
		h.push_back(0);
	}
	for(int i=0; i<m; i++){
		for(int j=0; j<n; j++){
			h[i+j]+=(f[i]*g[j]);
			h[i+j]%=MOD;
		}
	}
	return h;
}

int main()
{
	int n;
	scanf("%d", &n);
	vector<int> v[5000];
	for(int i=0; i<n-1; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		x--; y--;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	int d[5000];
	fill(d, d+n, -1);
	d[0]=0;
	queue<int> que;
	que.push(0);
	vector<P> dist;
	while(!que.empty()){
		int x=que.front();
		que.pop();
		dist.push_back(P(d[x], x));
		for(auto y:v[x]){
			if(d[y]<0){
				d[y]=d[x]+1;
				que.push(y);
			}
		}
	}
	sort(dist.begin(), dist.end(), greater<P>());
	int c[5000]={};
	for(auto p:dist){
		int x=p.second;
		for(auto y:v[x]){
			if(d[x]<d[y]) c[x]+=(c[y]+1);
		}
	}
	int cent;
	vector<int> s;
	bool reigai=0;
	for(int x=0; x<n; x++){
		bool ok=1;
		int sum=0;
		for(auto y:v[x]){
			if(d[x]<d[y]){
				sum+=(c[y]+1);
				if(c[y]+1>n/2) ok=0;
			}
		}
		if(n-1-sum>n/2) ok=0;
		if(ok){
			cent=x;
			if(n-1-sum>0) s.push_back(n-1-sum);
			for(auto y:v[x]){
				if(d[x]<d[y]) s.push_back(c[y]+1);
			}
			if(n%2!=0) break;
			for(auto x:s){
				if(x==n/2) reigai=1;
			}
			if(reigai){
				s.clear();
				s.push_back(n/2);
				s.push_back(n/2);
			}
			break;
		}
	}

	factorial();

	vector<ll> poly;
	poly.push_back(1);
	for(auto x:s){
		vector<ll> poly2;
		for(int i=0; i<=x; i++){
			ll t=f[x]*invf[x-i]%MOD*invf[i]%MOD*f[x]%MOD*invf[x-i]%MOD;
			poly2.push_back(t);
		}
		poly=polymul(poly, poly2);
	}

	ll ans=0;
	for(int i=0; i<n; i++){
		ll t=f[n-i]*poly[i]%MOD;
		if(i%2==1) t=MOD-t;
		ans+=t;
		ans%=MOD;
	}
	if(reigai){
		ans+=poly[n];
		ans%=MOD;
	}
	printf("%lld\n", ans);
    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 <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#define MOD 1000000007LL

using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

long long int powmod(long long int a, long long int k, long long int m){ //0<=a<=1e9, 0<k<=1e9+9, 0<m<=1e9+9
	if(a==0){
		return 0;
	}
	long long int apow[30];
	apow[0]=a;
	for(int i=1; i<30; i++){
		apow[i]=apow[i-1]*apow[i-1]%m;
	}
	long long int ans=1;
	for(int i=29; i>=0; i--){
		if(k>=(1ll<<i)){
			ans=ans*apow[i]%m;
			k-=(1ll<<i);
		}
	}
	return ans;
}
 
ll inv(ll x, ll p){
  return powmod(x, p-2, p);
}

ll f[5001], invf[5001];
void factorial(){
	f[0]=1;
	for(ll i=1; i<=5000; i++){
		f[i]=f[i-1]*i%MOD;
	}
	invf[5000]=inv(f[5000], MOD);
	for(ll i=4999; i>=0; i--){
		invf[i]=invf[i+1]*(i+1)%MOD;
	}
}

vector<ll> polymul(vector<ll> f, vector<ll> g){
	int m=f.size(), n=g.size();
	vector<ll> h;
	for(int k=0; k<m+n-1; k++){
		h.push_back(0);
	}
	for(int i=0; i<m; i++){
		for(int j=0; j<n; j++){
			h[i+j]+=(f[i]*g[j]);
			h[i+j]%=MOD;
		}
	}
	return h;
}

int main()
{
	int n;
	scanf("%d", &n);
	vector<int> v[5000];
	for(int i=0; i<n-1; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		x--; y--;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	int d[5000];
	fill(d, d+n, -1);
	d[0]=0;
	queue<int> que;
	que.push(0);
	vector<P> dist;
	while(!que.empty()){
		int x=que.front();
		que.pop();
		dist.push_back(P(d[x], x));
		for(auto y:v[x]){
			if(d[y]<0){
				d[y]=d[x]+1;
				que.push(y);
			}
		}
	}
	sort(dist.begin(), dist.end(), greater<P>());
	int c[5000]={};
	for(auto p:dist){
		int x=p.second;
		for(auto y:v[x]){
			if(d[x]<d[y]) c[x]+=(c[y]+1);
		}
	}
	int cent;
	vector<int> s;
	bool reigai=0;
	for(int x=0; x<n; x++){
		bool ok=1;
		int sum=0;
		for(auto y:v[x]){
			if(d[x]<d[y]){
				sum+=(c[y]+1);
				if(c[y]+1>n/2) ok=0;
			}
		}
		if(n-1-sum>n/2) ok=0;
		if(ok){
			cent=x;
			if(n-1-sum>0) s.push_back(n-1-sum);
			for(auto y:v[x]){
				if(d[x]<d[y]) s.push_back(c[y]+1);
			}
			if(n%2!=0) break;
			for(auto x:s){
				if(x==n/2) reigai=1;
			}
			if(reigai){
				s.clear();
				s.push_back(n/2);
				s.push_back(n/2);
			}
			break;
		}
	}

	factorial();

	vector<ll> poly;
	poly.push_back(1);
	for(auto x:s){
		vector<ll> poly2;
		for(int i=0; i<=x; i++){
			ll t=f[x]*invf[x-i]%MOD*invf[i]%MOD*f[x]%MOD*invf[x-i]%MOD;
			poly2.push_back(t);
		}
		poly=polymul(poly, poly2);
	}

	ll ans=0;
	for(int i=0; i<n; i++){
		ll t=f[n-i]*poly[i]%MOD;
		if(i%2==1) t=MOD-t;
		ans+=t;
		ans%=MOD;
	}
	if(reigai){
		ans+=poly[n];
		ans%=MOD;
	}
	printf("%lld\n", ans);
    return 0;
}
```