問題文
N 頂点の木 T が与えられます。i 番目の辺は頂点 Ai と Bi (1leqAi,BileqN) を結びます。
T の各頂点を、それぞれ独立に確率 1/2 で黒く、確率 1/2 で白く塗り、黒く塗られた頂点を全て含むような T の最小の部分木 (連結な部分グラフ) を S とします。(黒く塗られた頂点がないときは、S は空グラフとします。)
S の穴あき度を、S に含まれる白く塗られた頂点の個数とします。S の穴あき度の期待値を求めてください。
答えは有理数となるので、注記で述べるように bmod109+7 で出力してください。
注記
有理数を出力する際は、まずその有理数を分数 fracyx として表してください。ここで、x,y は整数であり、 x は 109+7 で割り切れてはなりません (この問題の制約下で、そのような表現は必ず可能です)。
そして、xzequivypmod109+7 を満たすような 0 以上 109+6 以下の唯一の整数 z を出力してください。
制約
- 2leqNleq2times105
- 1leqAi,BileqN
- 与えられるグラフは木である
入力
入力は以下の形式で標準入力から与えられる。
N
A1 B1
:
AN−1 BN−1
出力
S の穴あき度の期待値を bmod109+7 で出力せよ。
入力例 1
出力例 1
頂点 1,2,3 の色がそれぞれ 黒,白,黒 となったとき、S の穴あき度は 1 です。
それ以外の塗り方では S の穴あき度は 0 であるため、穴あき度の期待値は 1/8 です。
8times125000001equiv1pmod109+7 より、125000001 を出力します。
入力例 2
出力例 2
期待値は 3/8 です。
8times375000003equiv3pmod109+7 より、375000003 を出力します。
入力例 3
出力例 3
期待値は 1/4 です。
入力例 4
出力例 4