Description

Xiao A has a permutation $A_1$ through $A_{2^N}$ of $1$ through $2^N$. He wants to sort array $A$ in ascending order. Xiao A can perform $N$ types of operations, and each type can be used at most once. For every $i$ ($1 \le i \le N$), the $i$-th operation splits the sequence from left to right into $2^{N-i+1}$ blocks, each containing exactly $2^{i-1}$ numbers, and then swaps two of these blocks as a whole.

Xiao A wants to know how many different sequences of operations can sort array $A$ in ascending order. Two sequences of operations are considered different if and only if the number of operations is different, or at least one operation is different (either the type or the positions are different).

Here is an example of operations: $N = 3$, $A = [3,6,1,2,7,8,5,4]$.

• First operation: perform the 3rd operation, swap A[1..4] and A[5..8]. After the swap, $A = [7,8,5,4,3,6,1,2]$.
• Second operation: perform the 1st operation, swap A[3] and A[5]. After the swap, $A = [7,8,3,4,5,6,1,2]$.
• Third operation: perform the 2nd operation, swap A[1..2] and A[7..8]. After the swap, $A[1..8] = [1,2,3,4,5,6,7,8]$.

Input Format

The first line contains an integer $N$.

The second line contains $2^N$ integers, $A_1$ through $A_{2^N}$.

Output Format

Output a single integer denoting the answer.

3
7 8 5 6 1 2 4 3

6

Hint

Constraints: For 100% of the testdata, $1 \le N \le 12$.

Translated by ChatGPT 5