Independent Set

题意翻译

给一棵树，每一个点可以染成黑色或白色，任意两个相邻节点不能都是黑色，求方案数，结果对 $10^9+7$ 取模。

题目描述

[problemUrl]: https://atcoder.jp/contests/dp/tasks/dp_p $ N $ 頂点の木があります。 頂点には $ 1,\ 2,\ \ldots,\ N $ と番号が振られています。 各 $ i $ ($ 1\ \leq\ i\ \leq\ N\ -\ 1 $) について、$ i $ 番目の辺は頂点 $ x_i $ と $ y_i $ を結んでいます。 太郎君は、各頂点を白または黒で塗ることにしました。 ただし、隣り合う頂点どうしをともに黒で塗ってはいけません。 頂点の色の組合せは何通りでしょうか？ $ 10^9\ +\ 7 $ で割った余りを求めてください。

输入输出格式

输入格式


入力は以下の形式で標準入力から与えられる。 > $ 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

说明

### 制約 - 入力はすべて整数である。 - $ 1\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ x_i,\ y_i\ \leq\ N $ - 与えられるグラフは木である。 ### Sample Explanation 1 頂点の色の組合せは次図の $ 5 $ 通りです。 !\[\](https://img.atcoder.jp/dp/indep\_0\_muffet.png) ### Sample Explanation 2 頂点の色の組合せは次図の $ 9 $ 通りです。 !\[\](https://img.atcoder.jp/dp/indep\_1\_muffet.png)