配点 : $800$ 点

問題文

$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)$ を「パス $v$-$w$ に含まれる辺の本数」と定義します。

木の各頂点にはリスが $1$ 匹ずつ住んでいます。 リスたちは次のようにして引っ越しをすることにしました。 まず、$(1, 2, ..., N)$ の順列 $p = (p_1, p_2, ..., p_N)$ を自由にひとつ選びます。 その後、各 $1 \leq i \leq N$ について、頂点 $i$ に住んでいたリスは頂点 $p_i$ へ引っ越します。

リスたちは移動が好きなので、各リスの移動距離の総和が最大になるように引っ越しをすることにしました。 すなわち、$d(1, p_1) + d(2, p_2) + ... + d(N, p_N)$ が最大になるように $p$ を選ぶことにしました。 このような $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$ で割った余りを求めよ。

3
1 2
2 3

3

各リスの移動距離の総和の最大値は $4$ です。 条件を満たす $p$ は次の $3$ 通りです。

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

4
1 2
1 3
1 4

11

各リスの移動距離の総和の最大値は $6$ です。 例えば、$p = (2, 1, 4, 3)$ は条件を満たします。

6
1 2
1 3
1 4
2 5
2 6

36

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

396