← 返回题目列表

AtCoder · abc036_d

D. 图画书

中文机器翻译题面 查看原题

問題文

N 岛屿。 在岛上 它们的编号最大为 1 从 N 。 另外, 有N-1 桥梁。 i 这座桥是 a_i 数字岛和 b_i 它连接岛屿。 众所周知,任何岛屿都可以通过几座桥梁到达。
Snuke 决定将每个岛屿涂成白色或黑色。 但是,不应该有一座两端的岛屿都被漆成黑色的桥。 上色的方法有多少种? 除以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