Problem Statement

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$.

Sample Input 1

3
1 2
2 3

Sample Output 1

3

The maximum possible distance traveled by squirrels is $4$. There are three choices of $p$ that achieve it, as follows:

• $(2, 3, 1)$
• $(3, 1, 2)$
• $(3, 2, 1)$

Sample Input 2

4
1 2
1 3
1 4

Sample Output 2

11

The maximum possible distance traveled by squirrels is $6$. For example, $p = (2, 1, 4, 3)$ achieves it.

Sample Input 3

6
1 2
1 3
1 4
2 5
2 6

Sample Output 3

36

Sample Input 4

7
1 2
6 3
4 5
1 7
1 5
2 3

Sample Output 4

396