Inspired by the tv series Stranger Things, bear Limak is going for a walk between two mirror worlds.

There are two perfect binary trees of height H, each with the standard numeration of vertices from 1 to 2^H-1. The root is 1 and the children of x are 2 \cdot x and 2 \cdot x + 1.

Let L denote the number of leaves in a single tree, L = 2^{H-1}.

You are given a permutation P_1, P_2, \ldots, P_L of numbers 1 through L. It describes L special edges that connect leaves of the two trees. There is a special edge between vertex L+i-1 in the first tree and vertex L+P_i-1 in the second tree.

graph for sample1

drawing for the first sample test, permutation P = (2, 3, 1, 4), special edges in green

Let's define product of a cycle as the product of numbers in its vertices. Compute the sum of products of all simple cycles that have exactly two special edges, modulo (10^9+7).

A simple cycle is a cycle of length at least 3, without repeated vertices or edges.

Constraints

* 2 \leq H \leq 18
* 1 \leq P_i \leq L where L = 2^{H-1}
* P_i \neq P_j (so this is a permutation)

Input

Input is given from Standard Input in the following format (where L = 2^{H-1}).


H
P_1 P_2 \cdots P_L


Output

Compute the sum of products of simple cycles that have exactly two special edges. Print the answer modulo (10^9+7).

Examples

Input

3
2 3 1 4


Output

121788


Input

2
1 2


Output

36


Input

5
6 14 15 7 12 16 5 4 11 9 3 10 8 2 13 1


Output

10199246
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int Mod=1000000007;
int H;
#define Maxn 1000010
#define V 6000010
struct Node{
	int son[2],sum;
}tree[V];
int root[Maxn],cnt=0;
int val[Maxn],inval[Maxn],P[Maxn];
int inv[Maxn],L[Maxn],R[Maxn],invval[Maxn];
int pig[Maxn];
void dfs(int u){
	L[u]=R[u]=u;
	if(u*2<(1<<H)){
		val[u*2]=1ll*val[u]*(u*2)%Mod;
		invval[u*2]=1ll*invval[u]*inv[u*2]%Mod;
		dfs(u*2);
		L[u]=L[u*2];
	}
	if(u*2+1<(1<<H)){
		val[u*2+1]=1ll*val[u]*(u*2+1)%Mod;
		invval[u*2+1]=1ll*invval[u]*inv[u*2+1]%Mod;
		dfs(u*2+1);
		R[u]=R[u*2+1];
	}
}
void Insert(int &k,int x,int num,int add,int at){
	k=++cnt;
	tree[k]=tree[x];
	tree[k].sum+=add;if(tree[k].sum>=Mod)tree[k].sum-=Mod;
	if(at==-1)return;
	if(num&(1<<at))Insert(tree[k].son[1],tree[x].son[1],num,add,at-1);
	else Insert(tree[k].son[0],tree[x].son[0],num,add,at-1);
}

int main(){
	invval[0]=1;
	val[1]=1;invval[1]=1;
	scanf("%d",&H);
	inv[0]=inv[1]=1;
	for(int i=2;i<(1<<H);++i)inv[i]=1ll*(Mod-Mod/i)*inv[Mod%i]%Mod;
	dfs(1);
	for(int i=1;i<=(1<<(H-1));++i){
		scanf("%d",&P[i]);
		pig[i]=1ll*val[i+(1<<(H-1))-1]*val[P[i]+(1<<(H-1))-1]%Mod;
		Insert(root[i],root[i-1],P[i]+(1<<(H-1))-1,pig[i],H-2);
	}
	int Ans=0;
	for(int i=1;i<=(1<<(H-1));++i){
		int x=i+(1<<(H-1))-1,y=P[i]+(1<<(H-1))-1;
		for(int ancx=(x>>1),pre=x;ancx;pre=ancx,ancx>>=1){
			int k1,k2;
			if(pre==ancx*2){
				int tmpl=L[pre+1]-(1<<(H-1)),tmpr=R[pre+1]-(1<<(H-1))+1;
			    k1=root[tmpl],k2=root[tmpr];
			}else{
				int tmpl=L[pre-1]-(1<<(H-1)),tmpr=R[pre-1]-(1<<(H-1))+1;
				k1=root[tmpl],k2=root[tmpr];
			}
			int ancy=1,dir,tmp,tok1,tok2;
			int z=1ll*invval[ancx]*invval[ancx>>1]%Mod;
			for(int k=1;k<H;++k){
				int invz=1ll*z*invval[ancy]%Mod*invval[ancy>>1]%Mod;
				tmp=ancy*2;
				if(L[tmp]<=y&&y<=R[tmp])dir=0;
				else dir=1;
				if(dir==0){
				    tok1=tree[k1].son[1];tok2=tree[k2].son[1];
					Ans=(Ans+1ll*(tree[tok2].sum-tree[tok1].sum+Mod)*pig[i]%Mod*invz)%Mod;
					k1=tree[k1].son[0];k2=tree[k2].son[0];ancy=ancy*2;
				}else{
					tok1=tree[k1].son[0];tok2=tree[k2].son[0];
					Ans=(Ans+1ll*(tree[tok2].sum-tree[tok1].sum+Mod)*pig[i]%Mod*invz)%Mod;
					k1=tree[k1].son[1];k2=tree[k2].son[1];ancy=ancy*2+1;
				}
			}
		}
	}
	if(Ans%2==0)Ans/=2;
	else Ans=(Ans+Mod)/2;
	printf("%d\n",Ans);
	return 0;
}