Генеалогічне дерево#2851
На Іриному дні народження було багато родичів, через що було важко всіх впізнати. Щоб розібратися в ситуації, вирішили побудувати генеалогічне дерево. Однак через плутанину дерево вийшло не бінарним, хоча кількість вершин залишилася логічною — 2^k-1.
— Щось тут не так. — Справді? — Пропоную все перевірити. — Конкретніше? — Давайте розіб'ємо дерево на зв'язані частини по 2^i вершин, і кожен перевірить свою частину. — Чому саме так? — Не знаю, просто люблю ступені двійки. Крім того, у сумі вийде саме те, що треба. Але є одна проблема: способів це зробити надто багато. — Так, я пам'ятаю Судоку та заліковки. А скільки цього разу? — У тебе чудова пам'ять. Дай мені кілька хвилин подумати. — Будь ласка.
Перший рядок містить одне ціле число N=2^k-1 — кількість вершин у дереві (1 \leq k \leq 12). У наступному рядку наведено N-1 цілих чисел. Число a_i (1 \leq a_i < i+1) означає, що існує ребро між вершинами i+1 та a_i. Вершини пронумеровано починаючи з .
Виведіть одне ціле число — кількість способів розбити дерево на рівно зв'язаних блоків розмірів , , , ..., 2^{k-1}. Кожна вершина повинна входити рівно в один блок.
Приклад 1