Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Cleaning Robots

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe 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\}$$$.

Input

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 < 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.

Output

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$$$.

Examples

Input

6 1 3 2 3 3 4 4 5 4 6

Output

5

Input

5 1 2 2 3 2 4 4 5

Output

3

Note

Explanation for the sample input/output #1

This is the example from the problem description.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/22/2021 03:59:34 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|