Number of connected components P81115


Statement
 

pdf   zip

thehtml

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 ≤ 105, 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 108 + 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++