分数: 100 点
问题陈述
有一棵树 N 顶点,编号 1, 2, \ldots, N。 对于每个 i (1 \leq i \leq N - 1), i第一条边连接顶点 x_i 和 y_i.
Taro 决定将每个顶点绘制为白色或黑色。 这里,不允许将两个相邻的顶点都涂成黑色。
求顶点可绘制的方式数量,取模 10^9 + 7.
约束
- 输入中的所有值都是整数。
- 1 \leq N \leq 10^5
- 1 \leq x_i, y_i \leq N
- 给定的图是一棵树。
输入
输入由标准输入按以下格式给出:
N
x_1 y_1
x_2 y_2
:
x_{N - 1} y_{N - 1}
输出
打印顶点绘制方式的数量,取模 10^9 + 7.
样本输入 1
3 1 2 2 3
示例输出 1
5
绘制顶点有五种方法,如下:

示例输入 2
4 1 2 1 3 1 4
示例输出 2
9
绘制顶点的方法有九种,如下:

示例输入 3
1
示例输出 3
2
示例输入 4
10 8 5 10 8 6 5 1 5 4 8 2 10 3 6 9 2 1 7
示例输出 4
157