D - 塗り絵 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

N 個の島があります。 島には 1 から N までの番号がついています。 また、N-1 個の橋があります。 i 番目の橋は a_i 番の島と b_i 番の島をつないでいます。 どの島からどの島へも橋をいくつか経由して到達できることがわかっています。

すぬけ君は、それぞれの島を白または黒に塗ることにしました。 ただし、両端の島が黒で塗られているような橋があってはいけません。 色の塗り方が何通りあるか、10^9+7 で割った余りを求めてください。

制約

  • 2 ≤ N ≤ 10^5
  • 1 ≤ a_i, b_i ≤ N
  • どの島からどの島へも橋をいくつか経由して到達できる

入力

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

N
a_1 b_1
: 
a_{N-1} b_{N-1}

出力

色の塗り方が何通りあるか、10^9+7 で割った余りを出力せよ。

入力例1

5
2 5
1 5
2 4
3 2

出力例1

14

入力例2

10
7 9
8 1
9 6
10 8
8 6
10 3
5 8
4 8
2 5

出力例2

192