样例下载

题目描述

小明有一个 $1-2^N$ 的排列 $A[1..2^N]$, 他希望将 $A$ 数组从小到大排序,小明可以执行的操作有 $N$ 种,每种操作最多可以执行一次,对于所有的 $i(1<=i<=N)$,第 $i$ 种操作为将序列从左到右划分为 $2^{N-i+1}$ 段,每段恰好包括 $2^{i-1}$ 个数,然后整体交换其中两段.

小明想知道可以将数组 $A$ 从小到大排序的不同的操作序列有多少个。小明认为两个操作序列不同,当且仅当操作个数不同,或者至少一个操作不同(种类不同或者操作位置不同).

下面是一个操作事例: $N=3,A[1..8]$=$[3,6,1,2,7,8,5,4]$.

第一次操作,执行第 3 种操作,交换 $A[1..4]$ 和 $A[5..8]$,交换后的 $A[1..8]$ 为 $[7,8,5,4,3,6,1,2]$.

第二次操作,执行第 1 种操作,交换 $A[3]$和 $A[5]$,交换后的 $A[1..8]$ 为 $[7,8,3,4,5,6,1,2]$.

第三次操作,执行第 2 种操作,交换 $A[1..2]$ 和 $A[7..8]$,交换后的 $A[1..8]$ 为 $[1,2,3,4,5,6,7,8]$.

输入格式

第一行,一个整数 $N$

第二行, $2^N$ 个整数, $A[1..2^N]$

输出格式

一个整数表示答案

样例输入

3
7 8 5 6 1 2 4 3

样例输出

6

数据范围

有 10% 的数据：N = 3

有 30% 的数据：4 ≤ N ≤ 5

有 20% 的数据：N = 7

有 40% 的数据：10 ≤ N ≤ 12