题目描述

有一棵 $N$ 个顶点的树。顶点编号为 $1$ 到 $N$。第 $i$ 条边（$1 \leq i \leq N - 1$）连接顶点 $x_i$ 和 $y_i$。对于顶点 $v$ 和 $w$（$1 \leq v, w \leq N$），我们定义顶点 $v$ 和 $w$ 之间的距离 $d(v, w)$ 为 "路径上所包含的边的数量"。

每个顶点中都有一只松鼠。它们计划按照以下方式移动。首先，它们将自由选择一个排列 $(1, 2, ..., N)$，即 $p = (p_1, p_2, ..., p_N)$。然后，对于每个 $1 \leq i \leq N$，居住在顶点 $i$ 的松鼠将移动到顶点 $p_i$。

由于它们喜欢长途旅行，它们决定在此过程中最大化它们的总旅行距离。也就是说，它们将选择 $p$，使得 $d(1, p_1) + d(2, p_2) + ... + d(N, p_N)$ 最大化。有多少种满足条件的选择 $p$，取模 $10^9 + 7$？

约束条件

• $2 \leq N \leq 5,000$
• $1 \leq x_i, y_i \leq N$
• 输入树是一棵树。

输入

从标准输入读取输入数据。数据格式如下：

$N$ $x_1$ $y_1$ $x_2$ $y_2$ $:$ $x_{N - 1}$ $y_{N - 1}$

输出

输出满足条件的选择 $p$ 的数量，取模 $10^9 + 7$。

示例输入1

3
1 2
2 3

示例输出1

3

松鼠可以最大行进距离为 $4$。有三种满足条件的选择 $p$，如下所示：

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

示例输入2

4
1 2
1 3
1 4

示例输出2

11

松鼠可以最大行进距离为 $6$。例如，$p = (2, 1, 4, 3)$ 可以实现。

示例输入3

6
1 2
1 3
1 4
2 5
2 6

示例输出3

36

示例输入4

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

示例输出4

396