Xiao A has a permutation $A[1..2^N]$ of $1 \sim 2^N$, and he wants to sort the array $A$ in ascending order. Xiao A can perform $N$ types of operations, and each type of operation can be performed at most once. For all $i$ ($1 \le i \le N$), the $i$-th type of operation is: divide the sequence from left to right into $2^{N-i+1}$ segments, each containing exactly $2^{i-1}$ numbers, and then swap two of these segments. Xiao A wants to know how many different operation sequences can sort the array $A$ in ascending order. Xiao A considers two operation sequences to be different if and only if the number of operations is different, or at least one operation is different (different type or different position).

Below is an example of the operations: $N=3$, initial permutation $A[1..8]$ is $[3,6,1,2,7,8,5,4]$. First operation: Perform the 3rd type of operation, swap $A[1..4]$ and $A[5..8]$, the resulting $A[1..8]$ is $[7,8,5,4,3,6,1,2]$; Second operation: Perform the 1st type of operation, swap $A[3]$ and $A[5]$, the resulting $A[1..8]$ is $[7,8,3,4,5,6,1,2]$; Third operation: Perform the 2nd type of operation, swap $A[1..2]$ and $A[7..8]$, the resulting $A[1..8]$ is $[1,2,3,4,5,6,7,8]$.

Input

The first line contains an integer $N$. The second line contains $2^N$ integers, $A[1], A[2], \dots, A[2^N]$.

Output

A single line containing an integer, representing the number of different operation sequences that can sort the array $A$ in ascending order.

Constraints

For 30% of the data, $1 \le N \le 4$; For all data, $1 \le N \le 12$.

Examples

Input 1

3
7 8 5 6 1 2 4 3

Output 1

6