新的 ICPC 小镇有 $N$ 个路口（编号从 $1$ 到 $N$），由 $N-1$ 条道路连接。从任意一个路口出发，都可以通过一条或多条道路到达其他任何路口。为了确保所有路口都得到良好的维护，政府环境署计划部署他们最新的先进清洁机器人。除了清洁能力外，每个机器人还具备移动能力，使其能够从一个路口移动到由道路连接的任何其他路口。然而，正如你可能猜到的，这种机器人并不便宜。因此，该机构正在考虑以下部署计划。

令 $T_k$ 为第 $k$ 个机器人需要清洁的路口集合（也称为机器人的任务），且 $|T_k| \ge 1$ 为 $T_k$ 中的路口数量。$T_k$ 中的路口构成一条路径，即存在一个序列 $v_1, v_2, \dots, v_{|T_k|}$，其中 $v_i \in T_k$ 且对于所有 $i \neq j$ 都有 $v_i \neq v_j$，使得该序列中每两个相邻的路口都由一条道路连接。所有机器人的任务集合 $T$ 的并集等于 ICPC 小镇所有路口的集合。另一方面，没有两个机器人共享同一个路口，即如果 $i \neq j$，则 $T_i \cap T_j = \emptyset$。

为了避免市民对低效操作的投诉，部署计划必须是“不可约的”（irreducible）；换句话说，不存在两个机器人 $i$ 和 $j$，使得 $T_i \cup T_j$ 构成一条（更长的）路径。注意，只要所有任务都是不可约的，机构并不关心所使用的机器人数量是否最少。

你的任务是根据给定的小镇布局，计算可行部署计划的数量。一个计划是可行的，当且仅当它满足上述所有要求。

例如，设 $N = 6$，道路为 $\{(1, 3), (2, 3), (3, 4), (4, 5), (4, 6)\}$。如下图所示，共有 5 种可行的部署计划。

• 第一个计划使用 2 个机器人（图中标记为 A 和 B）来清洁 $\{1, 2, 3\}$ 和 $\{4, 5, 6\}$。
• 第二个计划使用 3 个机器人（图中标记为 A、B 和 C）来清洁 $\{1, 3, 4, 6\}$、$\{2\}$ 和 $\{5\}$。
• 第三个计划使用 3 个机器人来清洁 $\{1, 3, 4, 5\}$、$\{2\}$ 和 $\{6\}$。
• 第四个计划使用 3 个机器人来清洁 $\{1\}$、$\{2, 3, 4, 6\}$ 和 $\{5\}$。
• 第五个计划使用 3 个机器人来清洁 $\{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

样例输出 1

5

说明 1

这是题目描述中的示例。

样例输入 2

5
1 2
2 3
2 4
4 5

样例输出 2

3