Squirrel Migration

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

inputFormat

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}

outputFormat

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

样例

3
1 2
2 3

3