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

Genealogic tree

Genealogic tree

Лимит времени 1 секунда
Лимит использования памяти 256 MiB

На дне рожденья Иры было много родственников, так что знакомство с ними оказалось непростой задачей. Для того, чтобы получить общую картину, возникла идея составить генеалогическое дерево. В сумбурной обстановке как-то так получилось, что дерево оказалось не бинарным, хотя количество вершин было вполне логичным — 2^k-1.

Что-то тут не так. Да ну? Я предлагаю все перепроверить. Конкретнее. Разобьем дерево на связные части по2^iвершин и поручим каждому проверить свою часть. Почему именно так?Не знаю, люблю степени двойки, и к тому же в сумме будет ровно то, что надо. Хотя тут есть маленькая проблема, это можно сделать кучей способов. Да, я помню судоку и зачетки. Сколько же на этот раз? У тебя великолепная память, дай мне несколько минут на подумать. — Лови.

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

В первой строке дано число N=2^k-1 — количество вершин в дереве (1k12). В следующей строке дано N-1 число. a_i (1a_i < i+1) означает наличие ребра между вершинами i+1 и a_i. Вершины нумеруются с 1.

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

Вывести одно число — количество способов разделить дерево ровно на k связных блоков размеров 1, 2, 4, ..., 2^k-1. Каждая вершина должна попасть ровно в один блок.

Пример

Входные данные #1
7
1 1 2 2 3 3
Выходные данные #1
4