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