新的 ICPC 城镇有 $$$N$$$ 路口(编号从 $$$1$$$ 到 $$$N$$$),由 $$$N-1$$$ 道路连接。从一个路口可以通过一条或多条道路到达任何其他路口。为了确保所有路口得到良好维护,政府环境机构正计划部署最新的先进清洁机器人。除了清洁能力外,每个机器人还具备移动能力,可以从一个路口移动到任何由道路连接的其他路口。然而,正如您可能已经猜到的那样,此类机器人并不便宜。因此,该机构正在考虑以下部署计划。
设 $$$T_k$$$ 为 $$$k^{th}$$$ 机器人(也称为机器人的任务)应清洁的路口集合,$$$|T_k| \ge 1$$$ 是 $$$T_k$$$ 中的结点数量。 $$$T_k$$$ 中的交汇点形成一条路径,即存在 $$$v_1, v_2, \dots, v_{|T_k|}$$$ 序列,其中 $$$v_i \in T_k$$$ 和 $$$v_i \neq v_j$$$ 对于所有 $$$i \neq j$$$ ,使得该序列中的每个相邻交汇点都由道路连接。所有机器人$$$T$$$的并集等于ICPC镇中所有路口的集合。另一方面,没有两个机器人共享公共连接点,即 $$$T_i \cap T_j = \emptyset$$$ if $$$i \neq j$$$。
为了避免公民抱怨运作效率低下,部署计划应该是不可简化的;换句话说,不应该有两个机器人,$$$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\}$$$。
输入
输入以包含整数的行开头: $$$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
输入 #2
5 1 2 2 3 2 4 4 5
输出 #2
3
注意
示例输入/输出 #1 的说明
这是问题描述中的示例。