print2163. Дерево

printДерево

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В Небольшом королевстве живет и творит художник. Он был очень талантлив, творил все свое свободное время. Особенно хорошо у него получались деревья. Королеве очень нравились его картины, одну картину с деревом она даже повесила у себя в комнате.
Недавно до королевства дошел слух, что в скором времени состоится выставка картин. Короли и королевы разных королевств ценили те государства, в которых есть талантливые художники, часто посещали замки друг и друга и тесно сотрудничали. Поэтому королева Небольшого королевства решила послать на выставку одну из картин талантливого художника. Так как королевство было действительно небольшим, художник не могу себе позволить писать цветными красками, поэтому его картины были всегда черно-белыми. Королева хотела, чтобы картину ее королевства заметили на выставке, поэтому она приказала придворному аптекарю разработать два цвета красок: красный и зеленый, именно такие цвета были на флаге Небольшого королевства. Когда краски были готовы, художника заинтересовал другой вопрос, как раскрасить дерево.
Художник был талантлив, поэтому он придумал, как он будет раскрашивать свое дерево. Для каждого ребра дерева он выберет один из двух цветов и покрасит это ребро в выбранный цвет. Но он также знал, что королева предпочитает только интересно раскрашенные деревья. Интересно раскрашенными деревья королева считала такую раскраску, что в каждую вершину из ее потомка входит не более чем одно красное ребро.
Теперь художник, чтобы не быть наказанным, хотел раскрасить дерево так, чтобы оно стало интересно раскрашенным. Но он понял, что у одного дерева может существовать много раскрасок. Несмотря на то, что он был очень творческим человеком, ему было сложно сделать выбор, так как он этого никогда не делал.
Помогите художнику Небольшого королевства узнать, сколько различных интересных раскрасок дерева существует.
Так как это число может быть большим, вам нужно узнать остаток от деления количества раскрасок на `10^9\ +\ 7`.
В первой строке входного файла содержится число `n` – количество вершин в дереве `(1\ ≤\ n\ ≤\ 10^4)`.
Во второй строке задано `n\ -\ 1` чисел, каждое из которых `p_{i}` – номер той вершины, которая является предком вершины `i`.
Корень всегда имеет номер `0`.
В выходной файл выведите одно целое число – количество интересных раскрасок дерева по модулю `10^9\ +\ 7`.

Пример ввода 1

5
0 1 0 2

Пример вывода 1

12

Пример ввода 2

1

Пример вывода 2

1
Источник: neerc.ifmo.ru/school
loading