#include <stdio.h>
#include <vector>
using namespace std;

const long long mod = 1000000007;
long long inv[5050]={0,1},fact[5050]={1,1},ifact[5050]={1,1},cnt[5050]={1};

vector<int> G[5050];
int N,S[5050];

void go(int x, int l)
{
	S[x]++;
	for (auto y : G[x]) if (y != l){
		go(y,x);
		S[x] += S[y];
	}
}

int main()
{
	for (int i=2;i<5050;i++){
		inv[i] = (mod - mod / i) * inv[mod % i] % mod;
		fact[i] = fact[i-1] * i % mod;
		ifact[i] = ifact[i-1] * inv[i] % mod;
	}

	scanf ("%d",&N);

	for (int i=1;i<N;i++){
		int x,y; scanf ("%d %d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	go(1,0);

	for (int i=1;i<=N;i++){
		if (S[i] * 2 == N){
			printf ("%lld\n",fact[N/2]*fact[N/2]%mod);
			return 0;
		}
	}

	vector<int> sz;
	for (int i=1;i<=N;i++) if (N <= S[i] * 2){
		bool g = 1;
		for (int j : G[i]) if (S[i] > S[j] && S[j] * 2 > N) g = 0;
		if (g){
			sz.push_back(N - S[i]);
			for (int j : G[i]) if (S[i] > S[j]) sz.push_back(S[j]);
			break;
		}
	}

	for (auto s : sz){
		for (int j=N;j>=0;j--) if (cnt[j]){
			for (int k=1;k<=s;k++){
				long long seq = fact[s] * ifact[s-k] % mod;
				seq = seq * seq % mod * ifact[k] % mod;
				if (k & 1) cnt[j+k] = (cnt[j+k] + mod - cnt[j] * seq % mod) % mod;
				else cnt[j+k] = (cnt[j+k] + cnt[j] * seq % mod) % mod;
			}
		}
	}

	long long ans = 0;
	for (int j=0;j<=N;j++) ans = (ans + cnt[j] * fact[N-j]) % mod;
	printf ("%lld\n",ans);

	return 0;
}
### Prompt

Develop a solution in Cpp to the problem described below:

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 <vector>
using namespace std;

const long long mod = 1000000007;
long long inv[5050]={0,1},fact[5050]={1,1},ifact[5050]={1,1},cnt[5050]={1};

vector<int> G[5050];
int N,S[5050];

void go(int x, int l)
{
	S[x]++;
	for (auto y : G[x]) if (y != l){
		go(y,x);
		S[x] += S[y];
	}
}

int main()
{
	for (int i=2;i<5050;i++){
		inv[i] = (mod - mod / i) * inv[mod % i] % mod;
		fact[i] = fact[i-1] * i % mod;
		ifact[i] = ifact[i-1] * inv[i] % mod;
	}

	scanf ("%d",&N);

	for (int i=1;i<N;i++){
		int x,y; scanf ("%d %d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	go(1,0);

	for (int i=1;i<=N;i++){
		if (S[i] * 2 == N){
			printf ("%lld\n",fact[N/2]*fact[N/2]%mod);
			return 0;
		}
	}

	vector<int> sz;
	for (int i=1;i<=N;i++) if (N <= S[i] * 2){
		bool g = 1;
		for (int j : G[i]) if (S[i] > S[j] && S[j] * 2 > N) g = 0;
		if (g){
			sz.push_back(N - S[i]);
			for (int j : G[i]) if (S[i] > S[j]) sz.push_back(S[j]);
			break;
		}
	}

	for (auto s : sz){
		for (int j=N;j>=0;j--) if (cnt[j]){
			for (int k=1;k<=s;k++){
				long long seq = fact[s] * ifact[s-k] % mod;
				seq = seq * seq % mod * ifact[k] % mod;
				if (k & 1) cnt[j+k] = (cnt[j+k] + mod - cnt[j] * seq % mod) % mod;
				else cnt[j+k] = (cnt[j+k] + cnt[j] * seq % mod) % mod;
			}
		}
	}

	long long ans = 0;
	for (int j=0;j<=N;j++) ans = (ans + cnt[j] * fact[N-j]) % mod;
	printf ("%lld\n",ans);

	return 0;
}
```