CF1252B.Cleaning Robots

The new ICPC town has $N$ junctions (numbered from $1$ to $N$) which are connected by $N-1$ roads. It is possible from one junction to go to any other junctions by going through one or more roads. To make sure all the junctions are well-maintained, the government environment agency is planning to deploy their newest advanced cleaning robots. In addition to its cleaning ability, each robot is also equipped with a movement ability such that it can move from one junction to any other junctions connected by roads. However, as you might have guessed, such robots are not cheap. Therefore, the agency is considering the following deployment plan.

Let $T_k$ be the set of junctions which should be cleaned by the $k^{th}$ robot (also known as, the robot's task), and $|T_k| \ge 1$ be the number of junctions in $T_k$. The junctions in $T_k$ form a path, i.e. there exists a sequence of $v_1, v_2, \dots, v_{|T_k|}$ where $v_i \in T_k$ and $v_i \neq v_j$ for all $i \neq j$ such that each adjacent junction in this sequence is connected by a road. The union of $T$ for all robots is equal to the set of all junctions in ICPC town. On the other hand, no two robots share a common junction, i.e. $T_i \cap T_j = \emptyset$ if $i \neq j$.

To avoid complaints from citizens for an inefficient operation, the deployment plan should be irreducible; in other words, there should be no two robots, $i$ and $j$, such that $T_i \cup T_j$ forms a (longer) path. Note that the agency does not care whether the number of robots being used is minimized as long as all the tasks are irreducible.

Your task in this problem is to count the number of feasible deployment plan given the town's layout. A plan is feasible if and only if it satisfies all the above-mentioned requirements.

For example, let $N = 6$ and the roads are ${(1,3),(2,3),(3,4),(4,5),(4,6)}$. There are $5$ feasible deployment plans as shown in the following figure.

• The first plan uses $2$ robots (labeled as A and B in the figure) to clean ${1,2,3}$ and ${4,5,6}$.
• The second plan uses $3$ robots (labeled as A, B, and C in the figure) to clean ${1,3,4,6}$, ${2}$, and ${5}$.
• The third plan uses $3$ robots to clean ${1,3,4,5}$, ${2}$, and ${6}$.
• The fourth plan uses $3$ robots to clean ${1}$, ${2,3,4,6}$, and ${5}$.
• The fifth plan uses $3$ robots to clean ${1}$, ${2,3,4,5}$, and ${6}$.

No other plans are feasible in this case. For example, the plan ${{1,3},{2},{4,5,6}}$ is not feasible as the task ${1,3}$ and ${2}$ can be combined into a longer path ${1,3,2}$. The plan ${{1,2,3,4},{5},{6}}$ is also not feasible as ${1,2,3,4}$ is not a path.

新 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_k$ 的并集等于 ICPC 小镇的全部路口集合。另一方面，任意两台机器人所负责的路口集合互不相交，即当 $i \neq j$ 时，有 $T_i \cap T_j = \emptyset$。

为避免市民因运营效率低下而投诉，该部署方案必须是不可约的；换言之，不存在任意两台机器人 $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}$ 并非一条路径。

Input begins with a line containing an integer: $N$ ($1 \le N \le 100\,000$) representing the number of junctions. The next $N-1$ lines each contains two integers: $u_i$ $v_i$ ($1 \le u_i \lt v_i \le N$) representing a road connecting junction $u_i$ and junction $v_i$. It is guaranteed that it is possible from one junction to go to any other junctions by going through one or more roads.

输入的第一行包含一个整数：$N$（$1 \le N \le 100\,000$），表示路口的数量。接下来的 $N-1$ 行每行包含两个整数：$u_i$ 和 $v_i$（$1 \le u_i \lt v_i \le N$），表示一条连接路口 $u_i$ 和路口 $v_i$ 的道路。保证任意两个路口之间均可以通过一条或多条道路互相到达。

Output in a line an integer representing the number of feasible deployment plans. As this output can be large, you need to modulo the output by $1\,000\,000\,007$.

在一行中输出一个整数，表示可行的部署方案数量。由于该输出可能很大，你需要将结果对 $1\,000\,000\,007$ 取模。

Explanation for the sample input/output #1

This is the example from the problem description.

样例输入/输出 #1 的说明

这是题目描述中的示例。