#abc149f. [abc149_f]Surrounded Nodes

[abc149_f]Surrounded Nodes

問題文

NN 頂点の木 TT が与えられます。ii 番目の辺は頂点 AiA_iBiB_i (1leqAi,BileqN1 \\leq A_i,B_i \\leq N) を結びます。

TT の各頂点を、それぞれ独立に確率 1/21/2 で黒く、確率 1/21/2 で白く塗り、黒く塗られた頂点を全て含むような TT の最小の部分木 (連結な部分グラフ) を SS とします。(黒く塗られた頂点がないときは、SS は空グラフとします。)

SS穴あき度を、SS に含まれる白く塗られた頂点の個数とします。SS の穴あき度の期待値を求めてください。

答えは有理数となるので、注記で述べるように bmod109+7\\bmod 10^9+7 で出力してください。

注記

有理数を出力する際は、まずその有理数を分数 fracyx\\frac{y}{x} として表してください。ここで、x,yx,y は整数であり、 xx109+710^9+7 で割り切れてはなりません (この問題の制約下で、そのような表現は必ず可能です)。

そして、xzequivypmod109+7xz \\equiv y \\pmod{10^9+7} を満たすような 00 以上 109+610^9+6 以下の唯一の整数 zz を出力してください。

制約

  • 2leqNleq2times1052 \\leq N \\leq 2 \\times 10^5
  • 1leqAi,BileqN1 \\leq A_i,B_i \\leq N
  • 与えられるグラフは木である

入力

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

NN A1A_1 B1B_1 :: AN1A_{N-1} BN1B_{N-1}

出力

SS の穴あき度の期待値を bmod109+7\\bmod 10^9+7 で出力せよ。


入力例 1

3
1 2
2 3

出力例 1

125000001

頂点 1,2,31,2,3 の色がそれぞれ 黒,白,黒 となったとき、SS の穴あき度は 11 です。

それ以外の塗り方では SS の穴あき度は 00 であるため、穴あき度の期待値は 1/81/8 です。

8times125000001equiv1pmod109+78 \\times 125000001 \\equiv 1 \\pmod{10^9+7} より、125000001125000001 を出力します。


入力例 2

4
1 2
2 3
3 4

出力例 2

375000003

期待値は 3/83/8 です。

8times375000003equiv3pmod109+78 \\times 375000003 \\equiv 3 \\pmod{10^9+7} より、375000003375000003 を出力します。


入力例 3

4
1 2
1 3
1 4

出力例 3

250000002

期待値は 1/41/4 です。


入力例 4

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

出力例 4

570312505