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<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod=1e9+7;
const int bs=400;
int h,l,c[1<<18|10],p[1<<18],d[1<<18|10];
ll inv[1<<18],vl[1<<18],ivl[1<<18],ans;
struct evt{int l,r;ll v;};
vector<evt> ev[1<<18|10][2];
void Md(int&x){x>=mod && (x-=mod);}
void ins(int x,int v){
	int id=x/bs,up=l/bs;
	for(;x<min((id+1)*bs,l+1);x++)Md(c[x]+=v);
	for(id++;id<=up;id++)Md(d[id]+=v);
}
int qry(int x){
	int r=c[x]+d[x/bs];Md(r);
	return r;
}
int main(){
	scanf("%d",&h);l=1<<h-1;inv[1]=1;
	for(int i=2;i<2*l;i++)inv[i]=-mod/i*inv[mod%i]%mod;
	for(int i=0;i<2*l;i++){
		vl[i]=ivl[i]=1;
		for(int j=i;j;j/=2)(vl[i]*=j)%=mod,(ivl[i]*=inv[j])%=mod;
	}
	for(int i=0;i<l;i++){
		scanf("%d",p+i);p[i]--;
		ev[i][0].push_back({p[i],0,vl[i+l]*vl[p[i]+l]%mod});
		for(int j=i+l,k=0;j>1;j/=2,k++){
			if(j&1)continue;
			int lx=(j^1)<<k,rx=lx+(1<<k)-1;
			lx-=l,rx-=l;
			for(int pj=p[i]+l,pk=0;pj>1;pj/=2,pk++){
				int ly=(pj^1)<<pk,ry=ly+(1<<pk)-1;
				ly-=l,ry-=l;
				ll x=vl[i+l]*vl[p[i]+l]%mod*ivl[j/2]%mod*ivl[j/4]%mod*ivl[pj/2]%mod*ivl[pj/4]%mod;
				if(lx)ev[lx-1][1].push_back({ly,ry,-x});
				ev[rx][1].push_back({ly,ry,x});
			}
		}
	}
	for(int i=0;i<l;i++){
		for(evt&x:ev[i][0])
			ins(x.l+1,(x.v+mod)%mod);
		for(evt&x:ev[i][1])
			(ans+=(qry(x.r+1)-qry(x.l))*x.v)%=mod;
	}
	printf("%lld\n",(ans+mod)%mod);
	return 0;
}