题目描述

小Z听说了“红黑树”这个高级的概念，然而并没搞懂...

索性他自创了“红黑树”，就是对树上的每个节点进行红黑二选一的染色。

现在他想知道有多少种染色方法，使得整棵树及其每一个子树内两种颜色的数量相差不超过 $1$，结果对 $1e9+7$ 取模。

输入格式

$n$ 节点个数

$u,v$ 表示相连的一对点

输出格式

输入输出样例

2
1 2

2

$1,2$ 点分别染为红黑、黑红 $2$ 种方案

5
1 2
1 3
2 4
2 5

18

7
1 2
2 3
2 4
1 6
1 5
1 7

60

数据范围

$1\le n \le 3\times10^5,1\le u,v\le n$

其中 $10\%$ 的数据：$u_i+1=v_i$

另外 $10\%$ 的数据：给定为满二叉树