Genealogic tree
На дне рожденья Иры было много родственников, так что знакомство с ними оказалось непростой задачей. Для того, чтобы получить общую картину, возникла идея составить генеалогическое дерево. В сумбурной обстановке как-то так получилось, что дерево оказалось не бинарным, хотя количество вершин было вполне логичным — 2^k-1.
— Что-то тут не так. — Да ну? — Я предлагаю все перепроверить. — Конкретнее. — Разобьем дерево на связные части по 2^i вершин и поручим каждому проверить свою часть. — Почему именно так? — Не знаю, люблю степени двойки, и к тому же в сумме будет ровно то, что надо. Хотя тут есть маленькая проблема, это можно сделать кучей способов. — Да, я помню судоку и зачетки. Сколько же на этот раз? — У тебя великолепная память, дай мне несколько минут на подумать. — Лови.
Входные данные
В первой строке дано число N=2^k-1 — количество вершин в дереве (1 ≤ k ≤ 12). В следующей строке дано N-1 число. a_i (1 ≤ a_i < i+1) означает наличие ребра между вершинами i+1 и a_i. Вершины нумеруются с 1.
Выходные данные
Вывести одно число — количество способов разделить дерево ровно на k связных блоков размеров 1, 2, 4, ..., 2^k-1. Каждая вершина должна попасть ровно в один блок.