题目描述

新建的 ICPC 城镇共有 $N$ 个路口，编号为 $1$ 到 $N$。这些路口由 $N-1$ 条道路连接，并且从任意一个路口都可以沿道路到达任意其他路口，因此整个道路网络是一棵树。

为了保证所有路口都得到良好维护，政府环境部门计划部署最新型的高级清洁机器人。

除清洁能力外，每个机器人都能够沿道路在相邻路口之间移动。不过，这些机器人价格昂贵，因此管理部门制定了如下部署方案。

设第 $k$ 个机器人的任务为路口集合 $T_k$，并且：

$$|T_k|\ge 1.$$

集合 $T_k$ 中的路口必须构成一条路径。也就是说，存在一个序列

$$v_1,v_2,\ldots,v_{|T_k|},$$

满足：

• 每个 $v_i$ 都属于 $T_k$；
• 所有 $v_i$ 两两不同；
• 序列中每对相邻路口之间都有一条道路直接相连。

所有机器人的任务集合必须恰好覆盖全部路口，并且任意两个机器人不能负责同一个路口。形式化地：

$$\bigcup_k T_k=\{1,2,\ldots,N\},$$

且当 $i\ne j$ 时：

$$T_i\cap T_j=\varnothing.$$

为了避免市民抱怨部署方案效率低下，方案还必须是不可约的。

不可约的含义是：不存在两个不同的机器人 $i,j$，使得

$$T_i\cup T_j$$

仍然构成一条更长的路径。

管理部门并不要求使用的机器人数量最少，只要求所有任务满足上述不可约条件。

请计算给定道路结构下，合法部署方案的数量。

如果两个方案包含的任务集合划分不同，则视为不同方案；机器人本身没有编号，因此仅交换机器人编号不会产生新方案。

示例说明

当 $N=6$，道路为：

$$\{(1,3),(2,3),(3,4),(4,5),(4,6)\},$$

共有 $5$ 种合法部署方案。

这五种方案分别为：

1. $\{1,2,3\}$ 与 $\{4,5,6\}$；
2. $\{1,3,4,6\}$、$\{2\}$ 与 $\{5\}$；
3. $\{1,3,4,5\}$、$\{2\}$ 与 $\{6\}$；
4. $\{1\}$、$\{2,3,4,6\}$ 与 $\{5\}$；
5. $\{1\}$、$\{2,3,4,5\}$ 与 $\{6\}$。

例如，划分

$$\{\{1,3\},\{2\},\{4,5,6\}\}$$

不合法，因为任务 $\{1,3\}$ 与 $\{2\}$ 可以合并为路径 $\{1,3,2\}$。

划分

$$\{\{1,2,3,4\},\{5\},\{6\}\}$$

也不合法，因为 $\{1,2,3,4\}$ 本身并不构成一条路径。

输入格式

第一行包含一个整数 $N$：

$$1\le N\le 100\,000,$$

表示路口数量。

接下来 $N-1$ 行，每行包含两个整数 $u_i,v_i$：

$$1\le u_i<v_i\le N,$$

表示路口 $u_i$ 与 $v_i$ 之间有一条道路。

保证整张图连通。

输出格式

输出一个整数，表示合法部署方案的数量。

答案可能很大，请对

$$1\,000\,000\,007$$

取模后输出。

样例 1

输入

6
1 3
2 3
3 4
4 5
4 6

输出

5

样例 2

输入

5
1 2
2 3
2 4
4 5

输出

3