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>
#define LL long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
using namespace std;
namespace IO
{
    const int sz=1<<15;
    char inbuf[sz],outbuf[sz];
    char *pinbuf=inbuf+sz;
    char *poutbuf=outbuf;
    inline char _getchar()
    {
        if (pinbuf==inbuf+sz)fread(inbuf,1,sz,stdin),pinbuf=inbuf;
        return *(pinbuf++);
    }
    inline void _putchar(char x)
    {
        if (poutbuf==outbuf+sz)fwrite(outbuf,1,sz,stdout),poutbuf=outbuf;
        *(poutbuf++)=x;
    }
    inline void flush()
    {
        if (poutbuf!=outbuf)fwrite(outbuf,1,poutbuf-outbuf,stdout),poutbuf=outbuf;
    }
}
inline int read(){
	int v=0,f=1;
	char c=getchar();
	while (c<'0' || c>'9'){
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0' && c<='9'){
		v=v*10+c-'0';
		c=getchar();
	}
	return v*f;
}
const int Mod=1e9+7;
const int Maxn=262144;
int qp(int x,int p){
	int ret=1;
	while (p){
		if (p&1) ret=1ll*ret*x%Mod;
		p>>=1;
		x=1ll*x*x%Mod;
	}
	return ret;
}
int inv(int x){
	return qp(x,Mod-2);
}
const int mod=134217727;
int H,p[Maxn],n,hd[134217727],P[Maxn],iP[Maxn];
int nxt[42467388],cnt[42467388],ke;
LL val[42467388];

void Ins(LL X,int t){
	int pos=X&mod;
	int p=hd[pos];
	while (p!=-1 && val[p]!=X){
		p=nxt[p];
	}
	if (p!=-1){
		cnt[p]+=t;
		if (cnt[p]>=Mod) cnt[p]-=Mod;
	}
	else{
		cnt[ke]=t;val[ke]=X;nxt[ke]=hd[pos];hd[pos]=ke++;
	}
}
int Q(LL X){
	int pos=X&mod;
	for (int i=hd[pos];~i;i=nxt[i]){
		if (val[i]==X) return cnt[i];
	}
}
void Add(int&x,int y){
	x+=y;
	if (x>=Mod) x-=Mod;
}
int A[18][18];
signed main(){
	/*
	for (int i=70000000;i>=0;i--){
		int flag=1;
		for (int j=2;j*j<=i;j++){
			if (i%j==0) flag=0;
		}
		if (flag){
			cerr<<i<<endl;
			return 0; 
		}
	}*/
//	freopen("input.txt","r",stdin);
	for (int i=0;i<134217727;i++) hd[i]=-1;
	H=read();
	n=1<<H;
	P[1]=1;
	for (int i=2;i<n;i++){
		P[i]=1ll*P[i>>1]*i%Mod;
	}
	for (int i=1;i<n;i++){
		iP[i]=inv(P[i]);
		if (i>1){
			iP[i]=1ll*iP[i]*inv(P[i>>1])%Mod;
		} 
	}
	for (int i=n>>1;i<n;i++){
		p[i]=read();p[i]--;p[i]+=n>>1;
	//	cerr<<i<<' '<<p[i]<<endl;
		int d=1ll*P[i]*P[p[i]]%Mod;
		for (int j=i;j;j>>=1){
			for (int k=p[i];k;k>>=1) Ins((LL)j*Mod+k,d);
		}
	//	cerr<<i<<endl;
	}
//	cerr<<123<<endl;
	int ans=0;
	for (int i=n>>1;i<n;i++){
		
		for (int j=0;j<H;j++){
			for (int k=0;k<H;k++){
				LL v=((LL)(i>>j)*Mod)+(p[i]>>k);
				A[j][k]=Q(v);
			}
		}
		int bas=1ll*P[i]*P[p[i]]%Mod;
		for (int j=1;j<H;j++){
			for (int k=1;k<H;k++){
				int X=A[j][k]+A[j-1][k-1]-A[j-1][k]-A[j][k-1];
				if (X){
					Add(ans,1ll*bas*X%Mod*iP[i>>j]%Mod*iP[p[i]>>k]%Mod);
					if (ans<0) ans+=Mod;
				}
			}
		}
	}
	ans=1ll*ans*inv(2)%Mod;
	printf("%d\n",ans);
	return 0;
}