output_description: Print the expected holeyness of S, \bmod 10^9+7.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      A_1 B_1
      :
      A_{N-1} B_{N-1}
attempt: import sys
  from itertools import accumulate
  
  sys.setrecursionlimit(10**5)
  
  
  def dfs1(v, p):
      parent[v] = p
      stc = subtree_count[v]
      cnt = 1
      for u in links[v]:
          if u == p:
              continue
          result = dfs1(u, v)
          stc[u] = result
          cnt += result
      return cnt
  
  
  def dfs2(v, pc):
      # pc: vを根とした時の、parent方面の部分木のノード数
      global ans
  
      if len(subtree_count[v]) == 0:
          return
  
      p = parent[v]
      children, st_counts = map(list, zip(*subtree_count[v].items()))
      children.append(p)
      st_counts.append(pc)
      cl = len(st_counts)
      ct = sum(st_counts)
  
      for u, stc in subtree_count[v].items():
          dfs2(u, ct - stc + 1)
  
      if cl == 1:
          return
  
      prob_fwd = [0] + list(accumulate(st_counts[:-1]))
      prob_bwd = [0] + list(accumulate(st_counts[-1:0:-1]))
      prob_bwd.reverse()
      tmp = 0
      for pf, pb in zip(prob_fwd, prob_bwd):
          tmp = (tmp + d2s[pf + pb]) % MOD
      tmp = (tmp - d2s[ct] * (cl - 1)) % MOD
      ans = (ans + (1 - tmp) * d2) % MOD
  
  
  n = int(input())
  links = [set() for _ in range(n)]
  for line in sys.stdin:
      a, b = map(int, line.split())
      a -= 1
      b -= 1
      links[a].add(b)
      links[b].add(a)
  root = 0
  parent = [-1] * n
  subtree_count = [{} for _ in range(n)]  # 根がrootの時の、vの子の各部分木のノード数
  MOD = 10**9 + 7
  d2 = 500000004  # 2^-1 mod 10**9+7
  d2s = [1]
  for i in range(n):
      d2s.append(d2s[-1] * d2 % MOD)
  ans = 0
  dfs1(root, -1)
  # print(parent)
  # print(subtree_count)
  dfs2(root, 0)
  print(ans)
  
problem_description: 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.
samples: [{"input": "3\n    1 2\n    2 3", "output": "125000001\n    \n\nIf the vertices 1, 2, 3 are painted black, white, black, respectively, the\nholeyness of S is 1.\n\nOtherwise, the holeyness is 0, so the expected holeyness is 1/8.\n\nSince 8 \\times 125000001 \\equiv 1 \\pmod{10^9+7}, we should print 125000001.\n\n* * *"}, {"input": "4\n    1 2\n    2 3\n    3 4", "output": "375000003\n    \n\nThe expected holeyness is 3/8.\n\nSince 8 \\times 375000003 \\equiv 3 \\pmod{10^9+7}, we should print 375000003.\n\n* * *"}, {"input": "4\n    1 2\n    1 3\n    1 4", "output": "250000002\n    \n\nThe expected holeyness is 1/4.\n\n* * *"}, {"input": "7\n    4 7\n    3 1\n    2 6\n    5 2\n    7 1\n    2 7", "output": "570312505"}]