#-swank
(unless (member :child-sbcl *features*)
  (quit
   :unix-status
   (process-exit-code
    (run-program *runtime-pathname*
                 `("--control-stack-size" "128MB"
                   "--noinform" "--disable-ldb" "--lose-on-corruption" "--end-runtime-options"
                   "--eval" "(push :child-sbcl *features*)"
                   "--script" ,(namestring *load-pathname*))
                 :output t :error t :input t))))
;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (sb-int:defconstant-eqx OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0))
    #'equal)
  #+swank (ql:quickload '(:cl-debug-print :fiveam) :silent t)
  #-swank (set-dispatch-macro-character
           ;; enclose the form with VALUES to avoid being captured by LOOP macro
           #\# #\> (lambda (s c p) (declare (ignore c p)) `(values ,(read s nil nil t)))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)
#-swank (disable-debugger) ; for CS Academy

;; BEGIN_INSERTED_CONTENTS
;;;
;;; Modular arithmetic
;;;

;; Blankinship algorithm
;; Reference: https://topcoder.g.hatena.ne.jp/spaghetti_source/20130126/1359171466 (Japanese)
(declaim (ftype (function * (values fixnum fixnum &optional)) %ext-gcd))
(defun %ext-gcd (a b)
  (declare (optimize (speed 3) (safety 0))
           (fixnum a b))
  (let ((y 1)
        (x 0)
        (u 1)
        (v 0))
    (declare (fixnum y x u v))
    (loop (when (zerop a)
            (return (values x y)))
          (let ((q (floor b a)))
            (decf x (the fixnum (* q u)))
            (rotatef x u)
            (decf y (the fixnum (* q v)))
            (rotatef y v)
            (decf b (the fixnum (* q a)))
            (rotatef b a)))))

;; recursive version
;; (defun %ext-gcd (a b)
;;   (declare (optimize (speed 3) (safety 0))
;;            (fixnum a b))
;;   (if (zerop b)
;;       (values 1 0)
;;       (multiple-value-bind (p q) (floor a b) ; a = pb + q
;;         (multiple-value-bind (v u) (%ext-gcd b q)
;;           (declare (fixnum u v))
;;           (values u (the fixnum (- v (the fixnum (* p u)))))))))

;; TODO: deal with bignums
(declaim (inline ext-gcd))
(defun ext-gcd (a b)
  "Returns two integers X and Y which satisfy AX + BY = gcd(A, B)."
  (declare ((integer #.(- most-positive-fixnum) #.most-positive-fixnum) a b))
  (if (>= a 0)
      (if (>= b 0)
          (%ext-gcd a b)
          (multiple-value-bind (x y) (%ext-gcd a (- b))
            (declare (fixnum x y))
            (values x (- y))))
      (if (>= b 0)
          (multiple-value-bind (x y) (%ext-gcd (- a) b)
            (declare (fixnum x y))
            (values (- x) y))
          (multiple-value-bind (x y) (%ext-gcd (- a) (- b))
            (declare (fixnum x y))
            (values (- x) (- y))))))

(declaim (inline mod-inverse)
         (ftype (function * (values (mod #.most-positive-fixnum) &optional)) mod-inverse))
;; (defun mod-inverse (a modulus)
;;   "Solves ax ≡ 1 mod m. A and M must be coprime."
;;   (declare (integer a)
;;            ((integer 1 #.most-positive-fixnum) modulus))
;;   (mod (%ext-gcd (mod a modulus) modulus) modulus))

(defun mod-inverse (a modulus)
  (declare ((integer 1 #.most-positive-fixnum) modulus))
  (let ((a (mod a modulus))
        (b modulus)
        (u 1)
        (v 0))
    (declare (fixnum a b u v))
    (loop until (zerop b)
          for quot = (floor a b)
          do (decf a (the fixnum (* quot b)))
             (rotatef a b)
             (decf u (the fixnum (* quot v)))
             (rotatef u v))
    (setq u (mod u modulus))
    (if (< u 0)
        (+ u modulus)
        u)))

;;;
;;; Arithmetic operations with static modulus
;;;

(defmacro define-mod-operations (divisor)
  `(progn
     (defun mod* (&rest args)
       (reduce (lambda (x y) (mod (* x y) ,divisor)) args))

     (sb-c:define-source-transform mod* (&rest args)
       (if (null args)
           1
           (reduce (lambda (x y) `(mod (* ,x ,y) ,',divisor)) args)))

     (defun mod+ (&rest args)
       (reduce (lambda (x y) (mod (+ x y) ,divisor)) args))

     (sb-c:define-source-transform mod+ (&rest args)
       (if (null args)
           0
           (reduce (lambda (x y) `(mod (+ ,x ,y) ,',divisor)) args)))

     (define-modify-macro incfmod (delta)
       (lambda (x y) (mod (+ x y) ,divisor)))

     (define-modify-macro decfmod (delta)
       (lambda (x y) (mod (- x y) ,divisor)))

     (define-modify-macro mulfmod (multiplier)
       (lambda (x y) (mod (* x y) ,divisor)))))

(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
  "NOTE: cannot read -2^62"
  (declare #.OPT)
  (macrolet ((%read-byte ()
               `(the (unsigned-byte 8)
                     #+swank (char-code (read-char in nil #\Nul))
                     #-swank (sb-impl::ansi-stream-read-byte in nil #.(char-code #\Nul) nil))))
    (let* ((minus nil)
           (result (loop (let ((byte (%read-byte)))
                           (cond ((<= 48 byte 57)
                                  (return (- byte 48)))
                                 ((zerop byte) ; #\Nul
                                  (error "Read EOF or #\Nul."))
                                 ((= byte #.(char-code #\-))
                                  (setf minus t)))))))
      (declare ((integer 0 #.most-positive-fixnum) result))
      (loop
        (let* ((byte (%read-byte)))
          (if (<= 48 byte 57)
              (setq result (+ (- byte 48)
                              (* 10 (the (integer 0 #.(floor most-positive-fixnum 10))
                                         result))))
              (return (if minus (- result) result))))))))

(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

(defconstant +mod+ 1000000007)

;;;
;;; Body
;;;

(define-mod-operations +mod+)
(defun main ()
  (let* ((n (read))
         (graph (make-array n :element-type 'list :initial-element nil))
         (size (make-array n :element-type 'uint31))
         (powers (make-array 500000 :element-type 'uint31 :initial-element 1))
         (res (make-array n :element-type 'uint31)))
    (declare ((simple-array uint31 (*)) size powers res))
    (dotimes (i (- (length powers) 1))
      (setf (aref powers (+ i 1))
            (mod (ash (aref powers i) 1) +mod+)))
    (let ((/total (mod-inverse (aref powers n) +mod+)))
      #>/total
      (dotimes (i (- n 1))
        (let ((a (- (read-fixnum) 1))
              (b (- (read-fixnum) 1)))
          (push a (aref graph b))
          (push b (aref graph a))))
      (labels ((size-dfs (v parent)
                 (declare (int32 v parent))
                 (let ((res 1))
                   (declare (uint31 res))
                   (dolist (child (aref graph v))
                     (unless (= child parent)
                       (size-dfs child v)
                       (incf res (aref size child))))
                   (setf (aref size v) res)))
               (dfs (v parent)
                 (declare (int32 v parent))
                 (let ((sum (- (aref powers (- (aref size v) 1)) 1)))
                   (declare (fixnum sum))
                   (dolist (child (aref graph v))
                     (decf sum (- (aref powers (aref size child)) 1)))
                   (setf (aref res v) (mod* sum /total))
                   (dolist (child (aref graph v))
                     (unless (= child parent)
                       (decf (aref size v) (aref size child))
                       (incf (aref size child) (aref size v))
                       (dfs child v)
                       (decf (aref size child) (aref size v))
                       (incf (aref size v) (aref size child)))))))
        (size-dfs 0 -1)
        (dfs 0 -1)
        (println (mod (reduce #'+ res) +mod+))))))

#-swank (main)

;;;
;;; Test and benchmark
;;;

#+swank
(defun io-equal (in-string out-string &key (function #'main) (test #'equal))
  "Passes IN-STRING to *STANDARD-INPUT*, executes FUNCTION, and returns true if
the string output to *STANDARD-OUTPUT* is equal to OUT-STRING."
  (labels ((ensure-last-lf (s)
             (if (eql (uiop:last-char s) #\Linefeed)
                 s
                 (uiop:strcat s uiop:+lf+))))
    (funcall test
             (ensure-last-lf out-string)
             (with-output-to-string (out)
               (let ((*standard-output* out))
                 (with-input-from-string (*standard-input* (ensure-last-lf in-string))
                   (funcall function)))))))

#+swank
(defun get-clipbrd ()
  (with-output-to-string (out)
    ;; (run-program "C:/Windows/System32/WindowsPowerShell/v1.0/powershell.exe" '("get-clipboard") :output out)
    (run-program "powershell.exe" '("-Command" "Get-Clipboard") :output out :search t)))

#+swank (defparameter *this-pathname* (uiop:current-lisp-file-pathname))
#+swank (defparameter *dat-pathname* (uiop:merge-pathnames* "test.dat" *this-pathname*))

#+swank
(defun run (&optional thing (out *standard-output*))
  "THING := null | string | symbol | pathname

null: run #'MAIN using the text on clipboard as input.
string: run #'MAIN using the string as input.
symbol: alias of FIVEAM:RUN!.
pathname: run #'MAIN using the text file as input."
  (let ((*standard-output* out))
    (etypecase thing
      (null
       (with-input-from-string (*standard-input* (delete #\Return (get-clipbrd)))
         (main)))
      (string
       (with-input-from-string (*standard-input* (delete #\Return thing))
         (main)))
      (symbol (5am:run! thing))
      (pathname
       (with-open-file (*standard-input* thing)
         (main))))))

#+swank
(defun gen-dat ()
  (uiop:with-output-file (out *dat-pathname* :if-exists :supersede)
    (format out "")))

#+swank
(defun bench (&optional (out (make-broadcast-stream)))
  (time (run *dat-pathname* out)))

;; To run: (5am:run! :sample)
#+swank
(it.bese.fiveam:test :sample
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "3
1 2
2 3
"
    "125000001
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "4
1 2
2 3
3 4
"
    "375000003
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "4
1 2
1 3
1 4
"
    "250000002
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "7
4 7
3 1
2 6
5 2
7 1
2 7
"
    "570312505
")))


Measured memory_bytes: 54332