e-olymp
Yarışlar

July 12 - ADA Training

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

В стране есть n городов и n - 1 двусторонняя дорога, причем из каждого города можно добраться до любого другого города, двигаясь только по дорогам. Города пронумерованы целыми числами от 1 до n включительно.

Все дороги изначально плохие, однако правительство хочет улучшить состояние некоторых дорог. Будем считать, что граждане довольны улучшением дорог, если на пути от столицы, расположенной в городе 1, до любого города не более одной плохой дороги на пути.

Определите количество способов улучшить качество некоторых дорог так, чтобы удовлетворить требованиям граждан. Поскольку овет будет большим, выведите его по модулю 1 000 000 007 (109 + 7).

Входные данные

В первой строке задано одно целое число n (2 ≤ n ≤ 2 * 105) — количество городов в стране. В следующей строке задано n - 1 целое положительное число p2, p3, p4, ..., pn (1 ≤ pi ≤ i - 1) — описание дорог страны. Число pi означает, что в стране имеется дорога, соединяющая город pi и город i.

Выходные данные

Выведите искомое количество способов улучшить качество дорог по модулю 1 000 000 007 (109 + 7).

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
3
1 1
Çıxış verilənləri #1
4
Giriş verilənləri #2
6
1 2 2 1 5
Çıxış verilənləri #2
15