;; F - Surrounded Nodes

(defparameter *modulus* (+ (expt 10 9) 7))

(defun main ()
  (let* ((N (read))  ; 頂点数
         (tree (read-tree N)))
    (princ (solve N tree))
    (fresh-line)))

; (a) 自分が白 かつ (b) 隣接する部分グラフの2つ以上に黒が含まれる
; ならば, 自分はSに含まれる白頂点.
; 塗り分け方すべて: 2^N
; 自分が白: 2^(N - 1)
; (b) == not ((b1) or (b2))
; (b1) 隣接する部分グラフがすべて白: 1
; (b2) 隣接する部分グラフのちょうど一つGに黒が含まれる: 2^size(G) - 1
; 自分がSに含まれる白頂点である確率:
; (2^(N - 1) - 1 - sum_G (2^size(G) - 1))/2^N
; 全頂点の合計:
; (N * 2^(N - 1) - N - (sum_G 2^size(G)) + 2 * (N - 1))/2^N

(defun solve (N tree)
  (destructuring-bind
    ; 各頂点の親と各部分木の頂点数
    (parent subtree-size) (make-rooted-tree 0 tree)
    (let* ((subgraph-size ; 部分グラフの頂点数のリスト
             (loop for v below N append ; 各頂点
               (loop for next in (aref tree v) collect ; vの隣接頂点
                 ; nextの向こう側の部分グラフの頂点数
                 (if (eql next (aref parent v)) ; vの親?
                     (- N (aref subtree-size v))
                     (aref subtree-size next)))))
           (numerator (- (* N (1+ (ash 1 (1- N))))
                         (reduce #'+
                           (mapcar #'mod-expt-2
                             (normalize-exponents subgraph-size)))
                         2)))
    ; (2^N) * z == numerator mod *modulus* であるz
    ; *modulus*が素数なので 2^(*modulus* - 1) == 1 mod *modulus*
    (mod (* (mod numerator *modulus*) (mod-expt-2 (- *modulus* 1 N)))
         *modulus*))))

; 2, 2^100, 2^10000, 2^1000000 (mod *modulus*) のリスト
(defparameter *expt-2*
  (loop for n = 1 then (* n 100) while (< n *modulus*)
        collect (mod (ash 1 n) *modulus*)))

(defun mod-expt-2 (i)
  "(mod (expt 2 i) *modulus*)を少し速く計算"
  (mod (reduce #'*
         (loop for n = 1 then (* n 100)
               for x = i then (floor x 100) while (plusp x)
               for e in *expt-2*
               collect (expt e (mod x 100))))
       *modulus*))

(defun normalize-exponents (lst)
  "2の指数のリストを正規化"
  (setf lst (sort lst #'<))
  (labels ((normalizer (head n lst result)
             (cond ((and lst (eql (car lst) head))
                    (normalizer head (1+ n) (cdr lst) result))
                   ((>= n 2)
                    (normalizer (1+ head) (ash n -1) lst
                      (if (oddp n) (cons head result) result)))
                   (lst
                    (normalizer (car lst) 1 (cdr lst) (cons head result)))
                   (t (cons head result)))))
    (normalizer (car lst) 1 (cdr lst) ())))

(defun make-rooted-tree (root tree)
  "頂点rootを根としてtreeの各頂点の親を決める. 部分木の大きさも計算する."
  (let* ((N (array-dimension tree 0)) ; 頂点数
         (parent (make-array N :initial-element nil)) ; 親
         (subtree-size (make-array N :initial-element nil))) ; 部分木の頂点数
    (labels
      ((dfs (stack)
         (when stack
           (let ((v (pop stack)))
             (if (aref subtree-size v)
               ; 帰りがけ
               (loop for next in (aref tree v) ; vの隣接頂点
                 unless (eql next (aref parent v)) ; 親以外
                   do (incf (aref subtree-size v)
                            (aref subtree-size next)))
               ; 行きがけ
               (loop
                 initially (push v stack) ; 帰りがけ用に残す
                           (setf (aref subtree-size v) 1)
                 for next in (aref tree v) ; vの隣接頂点
                 unless (eql next (aref parent v)) ; 親以外
                   do (push next stack)
                      (setf (aref parent next) v))))
           (dfs stack))))
      (dfs (list root))
      (list parent subtree-size))))

(defun read-tree (N)
  "N頂点の木をreadして作る. 頂点番号は0〜N-1"
  (let ((tree (make-array N))) ; 隣接リスト
    (loop for i below N do (setf (aref tree i) nil))
    (loop repeat (1- N)
      do (let ((a (read-fixnum))
               (b (read-fixnum)))
           (push (1- b) (aref tree (1- a)))
           (push (1- a) (aref tree (1- b)))))
    tree))

(defun read-fixnum (&optional (in *standard-input*))
  "readより速い整数専用read. 
   参考: 競技プログラミングでCommon Lispを使っている人と
   これから使うかもしれない人のために, @sansaqua
   https://qiita.com/sansaqua/items/0b6417cb541047e29da4"
  (loop with acc = 0
        with minus = nil
        with started = nil
        for byte = (read-byte in)
        if (<= 48 byte 57)
          do (setf acc (+ (* acc 10) (- byte 48)))
             (setf started t)
        else if started
          return (if minus (- acc) acc)
        else if (= byte 45)
          do (setf minus t)))

(main)


Measured memory_bytes: 88548