F. Amir and Tree
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Akbar gave Amir a tree with $$$n$$$ vertices and told him that, If we root this tree from a non-leaf vertex, then value of $$$f(v)$$$ for each vertex is equal to :

  • If $$$v$$$ is a leaf, $$$f(v) = 1$$$.
  • Otherwise if $$$Sub(v)$$$ is defined as the set of vertices of subtree of $$$v$$$ which does not include $$$v$$$, then we have : $$$$$$f(v) = \sum_{A\ \subseteq\ Sub(v)}^{A\ \neq\ \varnothing} (\prod_{u\ \in A}^{} f(u))$$$$$$

$$$\prod_{}^{}$$$ works like $$$\sum_{}^{}$$$ but it calculates product instead of sum.

It is clear that by changing the root, the value of $$$f$$$ may change for different vertices.

Suppose we have rooted the tree from a vertex such that the value of $$$f(root)$$$ is minimum possible, Amir wants to know this value modulo $$$10^9 + 7$$$.

Note that according to the definition of function $$$f$$$, the root should not be a leaf!

Input

In the first line of input, you're given the number of vertices $$$n$$$.

$$$$$$3 \le n \le 10^5$$$$$$

In the next $$$n - 1$$$ lines, you'll receive two integers $$$u$$$ and $$$v$$$ which show that there's an edge between vertices $$$u$$$ and $$$v$$$.

$$$$$$1 \le u, v \le n$$$$$$

It is guaranteed that the given graph is a tree.

Output

Print the answer of the problem modulo $$$10^9 + 7$$$.

Examples
Input
7
1 2
2 3
2 4
2 5
3 6
3 7
Output
127
Input
3
1 2
2 3
Output
3
Note

Red numbers in the below pictures show $$$f(v)$$$.

The optimal root for the first sample is vertex $$$2$$$
The optimal root for the second sample is vertex $$$2$$$