题目描述

给定一棵 $n$ 个节点的无根树，对该树的节点进行黑白染色，要求任意两个黑点没有直接的边相连，求本质不同的染色方案模 $10^9+7$ 的余数。

如果两个染色方案所形成的树可以对节点重新标号后，使得对于任意编号为 $u$ 的节点，它在两棵树中只会同时为黑色或同时为白色，而且任意边 $(u,v)$ 在两棵树中只会同时存在或同时不存在，则称两个染色方案相同。

输入格式

第一行：一个整数 $n$，树上的结点数量；

第二行到第 $n$ 行：每行两个整数$u$和$v$，表示 $u$ 和 $v$ 连着一条边。

输出格式

单个整数：输出方案数模 $10^9+7$的余数。

1

2

5
1 2
1 3
1 4
1 5

6

6
1 2
1 3
1 4
4 5
4 6

9

样例分析

如上所述。

数据范围与提示

对于 $100\%$ 的数据：$1 \le n \leq 5\times 10^5$ 。