F - Surrounded Nodes /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600

問題文

N 頂点の木 T が与えられます。i 番目の辺は頂点 A_iB_i (1 \leq A_i,B_i \leq N) を結びます。

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

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

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

注記

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

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

制約

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

入力

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

N
A_1 B_1
:
A_{N-1} B_{N-1}

出力

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


入力例 1

3
1 2
2 3

出力例 1

125000001

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

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

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


入力例 2

4
1 2
2 3
3 4

出力例 2

375000003

期待値は 3/8 です。

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


入力例 3

4
1 2
1 3
1 4

出力例 3

250000002

期待値は 1/4 です。


入力例 4

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

出力例 4

570312505

Score : 600 points

Problem Statement

Given is a tree T with N vertices. The i-th edge connects Vertex A_i and B_i (1 \leq A_i,B_i \leq N).

Now, each vertex is painted black with probability 1/2 and white with probability 1/2, which is chosen independently from other vertices. Then, let S be the smallest subtree (connected subgraph) of T containing all the vertices painted black. (If no vertex is painted black, S is the empty graph.)

Let the holeyness of S be the number of white vertices contained in S. Find the expected holeyness of S.

Since the answer is a rational number, we ask you to print it \bmod 10^9+7, as described in Notes.

Notes

When you print a rational number, first write it as a fraction \frac{y}{x}, where x, y are integers, and x is not divisible by 10^9 + 7 (under the constraints of the problem, such representation is always possible).

Then, you need to print the only integer z between 0 and 10^9 + 6, inclusive, that satisfies xz \equiv y \pmod{10^9 + 7}.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq A_i,B_i \leq N
  • The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
A_1 B_1
:
A_{N-1} B_{N-1}

Output

Print the expected holeyness of S, \bmod 10^9+7.


Sample Input 1

3
1 2
2 3

Sample Output 1

125000001

If the vertices 1, 2, 3 are painted black, white, black, respectively, the holeyness of S is 1.

Otherwise, the holeyness is 0, so the expected holeyness is 1/8.

Since 8 \times 125000001 \equiv 1 \pmod{10^9+7}, we should print 125000001.


Sample Input 2

4
1 2
2 3
3 4

Sample Output 2

375000003

The expected holeyness is 3/8.

Since 8 \times 375000003 \equiv 3 \pmod{10^9+7}, we should print 375000003.


Sample Input 3

4
1 2
1 3
1 4

Sample Output 3

250000002

The expected holeyness is 1/4.


Sample Input 4

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

Sample Output 4

570312505