Length Of Circle

2 secs 1024 MB
sgsw

問題文


頂点数の木が与えられます。個の頂点はそれぞれ番号からまでを用いて表せるものとします。

行にわたって、入力が与えられ、個目の入力では、頂点と頂点が辺で繋がれているということが伝えられます。

グラフが好きなモジャくんは木を見て、以下のことに気が付きました。

◉「異なる頂点を選択して、点の間に(元々辺が存在するかに関わらず)新しい辺を結ぶと、ちょうどつだけ閉路ができる。」

モジャくんは、気になってできる閉路の長さの期待値を考えましたが、他の課題が迫っている中、落ち着いて考えることができませんでした。

モジャくんの代わりに閉路の長さの期待値を求めてください。

なお、ここでの期待値は、考えうる全てののペア通りに対する、閉路の長さの平均値と解釈できます。

制約


・与えられるグラフは木である。

・入力は全て整数値である。

入力


N
a_1 b_1
a_2 b_2
.
.
.
a_(N-1) b_(N-1)

出力


この問題の条件下では、求める期待値に対し

なる自然数のペアが一意に存在します。

を出力する代わりに、の範囲で一意に定まる、以上の自然数を出力してください。

最後に改行してください。

サンプル


入力1
2
1 2
出力1
2

です。より,となります。

入力2
5
1 2
2 3
5 4
2 4
出力2
399297744

です。より,となります。

入力3
20
1 10
2 8
14 12
4 15
17 18
20 6
16 1
3 5
6 8
11 3
6 12
19 4
17 13
7 10
10 13
4 6
9 6
4 1
3 8
出力3
220664546

です。より,となります。

Submit


Go (1.14)