#include<bits/stdc++.h>
using namespace std;

#define rep(i,l,r) for(register int i = l ; i <= r ; i++)
#define repd(i,r,l) for(register int i = r ; i >= l ; i--)
#define rvc(i,S) for(register int i = 0 ; i < (int)S.size() ; i++)
#define rvcd(i,S) for(register int i = ((int)S.size()) - 1 ; i >= 0 ; i--)
#define fore(i,x)for (register int i = head[x] ; i ; i = e[i].next)
#define forup(i,l,r) for (register int i = l ; i <= r ; i += lowbit(i))
#define fordown(i,id) for (register int i = id ; i ; i -= lowbit(i))
#define pb push_back
#define prev prev_
#define stack stack_
#define mp make_pair
#define fi first
#define se second
#define lowbit(x) (x&(-x))

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll,int> pr;

const int inf = 2e8;
const int maxn = 100020;
const ll mod = 1e9 + 7;
struct node{
	int next,to,w;
}e[maxn * 2];

int head[maxn],cnt,rt,sz[maxn],n,h[maxn];
ll f[maxn],fac[maxn],inv[maxn],g[maxn];

inline ll power(ll x,ll y){
	ll res = 1;
	while ( y ){
		if ( y & 1) res = res * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
void init(){
	fac[0] = inv[0] = 1;
	rep(i,1,n) fac[i] = fac[i - 1] * i % mod , inv[i] = power(fac[i],mod - 2);	
}

inline void adde(int x,int y){
	e[++cnt].to = y;
	e[cnt].next = head[x];
	head[x] = cnt;
}
inline void up(ll &x,ll y){ x = (x + y) % mod; }
inline ll C(int n,int m){
	if ( n < 0 || m < 0 || n < m ) return 0;
	return fac[n] * inv[m] % mod * inv[n - m]  %mod;
}
void dfs(int x,int fa){
	sz[x] = 1; int mx = 0;
	fore(i,x){
		if ( e[i].to == fa ) continue;
		dfs(e[i].to,x);
		sz[x] += sz[e[i].to];
		mx = max(mx,sz[e[i].to]);
	}
	mx = max(mx,n - sz[x]);
	if ( !rt || mx < h[rt] ) rt = x;
	h[x] = mx;
}
void dfs2(int x,int fa){
	sz[x] = 1;
	fore(i,x){
		if ( e[i].to == fa ) continue;
		dfs2(e[i].to,x);
		sz[x] += sz[e[i].to];
	}
}
int main(){
	scanf("%d",&n);
	rep(i,1,n - 1){
		int x,y;
		scanf("%d %d",&x,&y);
		adde(x,y) , adde(y,x);
	}
	init();
	dfs(1,0);
	f[0] = 1 , sz[rt] = 1;
//	cout<<rt<<endl;
	fore(i,rt){
	   	dfs2(e[i].to,rt);
		rep(j,0,sz[rt]) g[j] = f[j] , f[j] = 0;
		rep(j,0,sz[rt]) rep(k,0,sz[e[i].to]){
//			if ( j - 2 * k  + sz[e[i].to] < 0 ) break;
			up(f[j + k],g[j] * C(sz[e[i].to],k) % mod * C(sz[e[i].to],k) % mod * fac[k]);
		}
		sz[rt] += sz[e[i].to];
//		rep(j,0,sz[rt]) cout<<f[j]<<" ";
//		cout<<endl;
	}
	ll ans = 0;
	rep(i,0,n){
		ll tp = (i & 1) ? -1 : 1;
		up(ans,f[i] * tp * fac[n - i]);
	}
	cout<<(ans + mod)% mod<<endl;
}


### Prompt

Please create a solution in Cpp 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>
using namespace std;

#define rep(i,l,r) for(register int i = l ; i <= r ; i++)
#define repd(i,r,l) for(register int i = r ; i >= l ; i--)
#define rvc(i,S) for(register int i = 0 ; i < (int)S.size() ; i++)
#define rvcd(i,S) for(register int i = ((int)S.size()) - 1 ; i >= 0 ; i--)
#define fore(i,x)for (register int i = head[x] ; i ; i = e[i].next)
#define forup(i,l,r) for (register int i = l ; i <= r ; i += lowbit(i))
#define fordown(i,id) for (register int i = id ; i ; i -= lowbit(i))
#define pb push_back
#define prev prev_
#define stack stack_
#define mp make_pair
#define fi first
#define se second
#define lowbit(x) (x&(-x))

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll,int> pr;

const int inf = 2e8;
const int maxn = 100020;
const ll mod = 1e9 + 7;
struct node{
	int next,to,w;
}e[maxn * 2];

int head[maxn],cnt,rt,sz[maxn],n,h[maxn];
ll f[maxn],fac[maxn],inv[maxn],g[maxn];

inline ll power(ll x,ll y){
	ll res = 1;
	while ( y ){
		if ( y & 1) res = res * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
void init(){
	fac[0] = inv[0] = 1;
	rep(i,1,n) fac[i] = fac[i - 1] * i % mod , inv[i] = power(fac[i],mod - 2);	
}

inline void adde(int x,int y){
	e[++cnt].to = y;
	e[cnt].next = head[x];
	head[x] = cnt;
}
inline void up(ll &x,ll y){ x = (x + y) % mod; }
inline ll C(int n,int m){
	if ( n < 0 || m < 0 || n < m ) return 0;
	return fac[n] * inv[m] % mod * inv[n - m]  %mod;
}
void dfs(int x,int fa){
	sz[x] = 1; int mx = 0;
	fore(i,x){
		if ( e[i].to == fa ) continue;
		dfs(e[i].to,x);
		sz[x] += sz[e[i].to];
		mx = max(mx,sz[e[i].to]);
	}
	mx = max(mx,n - sz[x]);
	if ( !rt || mx < h[rt] ) rt = x;
	h[x] = mx;
}
void dfs2(int x,int fa){
	sz[x] = 1;
	fore(i,x){
		if ( e[i].to == fa ) continue;
		dfs2(e[i].to,x);
		sz[x] += sz[e[i].to];
	}
}
int main(){
	scanf("%d",&n);
	rep(i,1,n - 1){
		int x,y;
		scanf("%d %d",&x,&y);
		adde(x,y) , adde(y,x);
	}
	init();
	dfs(1,0);
	f[0] = 1 , sz[rt] = 1;
//	cout<<rt<<endl;
	fore(i,rt){
	   	dfs2(e[i].to,rt);
		rep(j,0,sz[rt]) g[j] = f[j] , f[j] = 0;
		rep(j,0,sz[rt]) rep(k,0,sz[e[i].to]){
//			if ( j - 2 * k  + sz[e[i].to] < 0 ) break;
			up(f[j + k],g[j] * C(sz[e[i].to],k) % mod * C(sz[e[i].to],k) % mod * fac[k]);
		}
		sz[rt] += sz[e[i].to];
//		rep(j,0,sz[rt]) cout<<f[j]<<" ";
//		cout<<endl;
	}
	ll ans = 0;
	rep(i,0,n){
		ll tp = (i & 1) ? -1 : 1;
		up(ans,f[i] * tp * fac[n - i]);
	}
	cout<<(ans + mod)% mod<<endl;
}


```