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?

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.

Constraints

• $2 \leq N \leq 5,000$
• $1 \leq x_i, y_i \leq N$
• The input graph is a tree.

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

见题面 Input 部分

见题面 Output 部分