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;
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pa pair<int,int>
#define mod 1000000007
#define ll long long
#define mk make_pair
#define pb push_back
#define fi first
#define se second
#define cl(x) memset(x,0,sizeof x)
#ifdef Devil_Gary
#define bug(x) cout<<(#x)<<" "<<(x)<<endl
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define bug(x)
#define debug(...)
#endif

const int INF = 0x7fffffff;
const int N=6e5+5;
/*
char *TT,*mo,but[(1<<15)+2];
#define getchar() ((TT==mo&&(mo=(TT=but)+fread(but,1,1<<15,stdin),TT==mo))?-1:*TT++)//*/
inline int read(){
    int x=0,rev=0,ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')rev=1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return rev?-x:x;
}/*
struct Edge{
	int nxt,v;
//	int w;
//	int id;
}e[N<<1];
void add(int u,int v){
	e[++tot].v=v,e[tot].nxt=head[u],head[u]=tot;
	e[++tot].v=u,e[tot].nxt=head[v],head[v]=tot;
}*/
ll n,m,ans,a[N],t[N],val[N];
void add(int l,int r,int op,int pos){
//	bug(1);
//cerr<<l<<" "<<r<<endl;
	ll ret,tt,p2;
	for(int i=l;i<=r;i++){
		tt=0,ret=1,p2=a[i]+(n/2)-1;
//		bug(p2),bug(val[i]);
		while(p2){
//			bug(p2); 
			if(!op) (t[p2]+=val[i]*ret)%=mod;
			else (ans+=(t[p2]-tt+mod)*ret%mod*val[i]%mod*p2%mod*pos%mod)%=mod,(tt=t[p2]*p2%mod)%=mod;
			ret=ret*p2%mod,p2>>=1;
		}
	}
}
void clear(int l,int r){
	for(int i=l;i<=r;i++){
		int p2=a[i]+(n/2)-1;
		while(p2){
			t[p2]=0,p2>>=1;
		}
	}
}
void dfs(int pos,int l,int r){
	if(l==r) {
		val[l]=1LL;
//		bug(1);
//		bug(pos);
		return;
	}
	
	int mid=l+r>>1;
	dfs(pos<<1,l,mid),dfs(pos<<1|1,mid+1,r);
	
	for(int i=l;i<=mid;i++) val[i]=val[i]*(pos<<1)%mod;
	for(int i=mid+1;i<=r;i++) val[i]=val[i]*(pos<<1|1)%mod;
	
	add(l,mid,0,pos),add(mid+1,r,1,pos);
	clear(l,r);
//	for(int i=l;i<=mid;i++)
}
int main(){
#ifdef Devil_Gary
    freopen("in.txt","r",stdin);
//  freopen("out.txt","w",stdout);
#endif	
	m=read(),n=pow(2,m);
	for(int i=1;i<=n/2;i++) a[i]=read();
	dfs(1,1,n/2);
	cout<<ans<<endl;
	return 0;
}
