eolymp
bolt
Try our new interface for solving problems
Problems

Roads Improvement

Roads Improvement

The country has $n$ cities and $n - 1$ bidirectional roads, it is possible to get from every city to any other one if you move only along the roads. The cities are numbered with integers from $1$ to $n$ inclusive. All the roads are initially bad, but the government wants to improve the state of some roads. We will assume that the citizens are happy about road improvements if the path from the capital, located in city $1$, to any other city contains at most one bad road. Determine the number of ways to improve the quality of some roads to meet the citizens' needs. As the answer can be large, print it modulo $10^9 + 7$. \InputFile The first line contains a single integer $n~(2 \le n \le 2 \cdot 10^5)$ --- the number of cities in the country. The next line contains $n - 1$ positive integers $p_2, p_3, p_4, \cdots, p_n~(1 \le p_i \le i - 1)$ --- the description of the roads in the country. The number $p_i$ means that the country has a road connecting city $p_i$ and city $i$. \OutputFile Print the number of ways to improve the quality of the roads modulo $10^9 + 7$. \includegraphics{https://eolympusercontent.com/images/jcimtjhs514ktd6nbudm1og03s.gif}
Time limit 1 second
Memory limit 128 MiB
Input example #1
3
1 1
Output example #1
4
Input example #2
6
1 2 2 1 5
Output example #2
15