eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Улучшение дорог

Улучшение дорог

В стране есть $n$ городов и $n - 1$ двусторонняя дорога, причем из каждого города можно добраться до любого другого города, двигаясь только по дорогам. Города пронумерованы целыми числами от $1$ до $n$ включительно. Все дороги изначально плохие, однако правительство хочет улучшить состояние некоторых дорог. Будем считать, что граждане довольны улучшением дорог, если на пути от столицы, расположенной в городе $1$, до любого города не более одной плохой дороги на пути. Определите количество способов улучшить качество некоторых дорог так, чтобы удовлетворить требованиям граждан. Поскольку ответ будет большим, выведите его по модулю $10^9 + 7$. \InputFile В первой строке задано одно целое число $n~(2 \le n \le 2 \cdot 10^5)$ --- количество городов в стране. В следующей строке задано $n - 1$ целое положительное число $p_2, p_3, p_4, \cdots, p_n~(1 \le p_i \le i - 1)$ --- описание дорог страны. Число $p_i$ означает, что в стране имеется дорога, соединяющая город $p_i$ и город $i$. \OutputFile Выведите искомое количество способов улучшить качество дорог по модулю $10^9 + 7$. \includegraphics{https://eolympusercontent.com/images/jcimtjhs514ktd6nbudm1og03s.gif}
Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
3
1 1
Выходные данные #1
4
Входные данные #2
6
1 2 2 1 5
Выходные данные #2
15