题目描述

$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$ で割った余りを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

条件を満たすような $p$ の選び方は何通りあるか？ $10^9\ +\ 7$ で割った余りを求めよ。

题目大意

给你一个$N$个节点的树，求一个$1\cdots N$的排列$(p_1,p_2,\cdots p_N)$ ，使得$\sum dist(i,p_i)$最大。

求这样的排列的个数。答案对$10^9+7$取模。

3
1 2
2 3

3

4
1 2
1 3
1 4

11

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

提示

制約

• $2\ \leq\ N\ \leq\ 5,000$
• $1\ \leq\ x_i,\ y_i\ \leq\ N$
• 入力のグラフは木である。

Sample Explanation 1

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

Sample Explanation 2

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