You are given a tree, that is, an undirected, connected graph with no cycles. Can you count how many (non-empty) connected subgraphs it contains?

Input

Input consists of several trees,
each one with the number of vertices n,
followed by its n − 1 edges.
You can assume 1 ≤ n ≤ 10^{5},
that vertices are numbered between 0 and n − 1,
and that the given edges indeed form a tree.

Output

For every given tree,
print its number of connected subgraphs.
As this number may be large,
make the computations modulo 10^{8} + 7.

Public test cases

**Input**

1 2 1 0 3 2 0 1 2 4 0 3 0 2 0 1 4 3 2 2 1 1 0 7 1 6 0 4 4 2 4 3 4 6 3 5

**Output**

1 3 6 11 10 44

Information

- Author
- Edgar Moreno
- Language
- English
- Official solutions
- C++
- User solutions
- C++