题目描述

小 A 有一个 $1 \sim 2 ^ n$ 的排列 $A[1 \ldots 2 ^ n]$，他希望将 $A$ 数组从小到大排序，小 A 可以执行的操作有 $n$ 种，每种操作最多可以执行一次，对于所有的 $i$（$1 \leq i \leq n$），第 $i$ 种操作为将序列从左到右划分为 $2 ^ {n - i + 1}$ 段，每段恰好包括 $2 ^ {i - 1}$ 个数，然后整体交换其中两段。小 A 想知道可以将数组 A 从小到大排序的不同的操作序列有多少个，小 A 认为两个操作序列不同，当且仅当操作个数不同，或者至少一个操作不同（种类不同或者操作位置不同）。

下面是一个操作示例：$n = 3, A[1 \ldots 8] = [3, 6, 1, 2, 7, 8, 5, 4]$。
第一次操作，执行第三种操作，交换 $A[1 \ldots 4]$ 和 $A[5 \ldots 8]$，交换后的 $A[1 \ldots 8]$ 为 $[7,8,5,4,3,6,1,2]$；
第二次操作，执行第一种操作，交换 $A[3]$ 和 $A[5]$，交换后的 $A[1 \ldots 8]$ 为 $[7,8,3,4,5,6,1,2]$；
第三次操作，执行第二种操作，交换 $A[1 \ldots 2]$ 和 $A[7 \ldots 8]$，交换后的 $A[1 \ldots 8]$ 为 $[1,2,3,4,5,6,7,8]$。

输入格式

第一行一个整数 $n$。
第二行 $2 ^ n$ 个整数，表示 $A[1 \ldots 2 ^ n]$。

输出格式

一个整数表示答案。

样例

3
7 8 5 6 1 2 4 3

6

数据范围与提示

$1 \leq N \leq 12$