Genealogic tree#2851
There were many relatives at Ira's birthday, making it difficult to recognize them all. To understand the overall picture, the idea of constructing a genealogical tree arose. However, due to the confusion, the tree turned out not to be binary, although the number of vertices was logical — 2^k-1.
— Something is not right here. — Really? — I propose we double-check everything. — Specifically? — Let's split the tree into connected parts of 2^i vertices, and have each person check their part. — Why exactly like this? — I don't know, I just like powers of two. Besides, the total will be exactly what we need. But there is a small problem: there are many ways to do it. — Yes, I remember Sudoku and record-books. How many ways are there this time? — You have an excellent memory. Give me a few minutes to think. — Go ahead.
The first line contains an integer N=2^k-1 — the number of vertices in the tree (1 \leq k \leq 12). The next line contains N-1 integers. Integer a_i (1 \leq a_i < i+1) indicates that there is an edge between vertices i+1 and a_i. Vertices are numbered starting from .
Print a single integer — the number of ways to divide the tree into exactly connected blocks of sizes , , , ..., 2^{k-1}. Each vertex must belong to exactly one block.
Example 1