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 clr(x) memset(x,0,sizeof (x))
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define fi first
#define se second
#define kill _z_kill
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define outval(x) cerr<<#x" = "<<x<<endl
#define outv(x) cerr<<#x" = "<<x<<"  "
#define outtag(x) cerr<<"--------------"#x"---------------"<<endl
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
	For(_x,L,R) cerr<<a[_x]<<" ";cerr<<endl;
#define User_Time ((double)clock()/CLOCKS_PER_SEC)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned uint;
typedef long double LD;
typedef vector <int> vi;
typedef pair <int,int> pii;
LL read(){
	LL x=0,f=0;
	char ch=getchar();
	while (!isdigit(ch))
		f=ch=='-',ch=getchar();
	while (isdigit(ch))
		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
template <class T> void ckmax(T &x,const T y){
	if (x<y)
		x=y;
}
template <class T> void ckmin(T &x,const T y){
	if (x>y)
		x=y;
}
const int mod=1e9+7;
int Pow(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=(LL)x*x%mod)
		if (y&1)
			ans=(LL)ans*x%mod;
	return ans;
}
void Add(int &x,int y){
	if ((x+=y)>=mod)
		x-=mod;
}
void Del(int &x,int y){
	if ((x-=y)<0)
		x+=mod;
}
int Add(int x){
	return x>=mod?x-mod:x;
}
int Del(int x){
	return x<0?x+mod:x;
}
const int N=1<<18,S=N*20*2;
int n,s;
int val[N],ival[N];
int lp[N],rp[N];
int ans=0;
int tmp;
namespace seg{
	int cnt=0;
	int val[S],ls[S],rs[S],xp[S];
	int ins(int rt,int x,int p,int v){
		if (!rt)
			rt=++cnt,xp[rt]=x;
		Add(val[rt],v);
		if (x>=(1<<n)){
			assert(x==p);
			return rt;
		}
		if (p<=rp[x*2])
			ls[rt]=ins(ls[rt],x*2,p,v);
		else
			rs[rt]=ins(rs[rt],x*2+1,p,v);
		return rt;
	}
	int merge(int x,int y,int a){
		if (!x||!y)
			return x|y;
		if (a>=(1<<n)){
			int rt=++cnt;
			val[rt]=Add(val[x]+val[y]);
			xp[rt]=a;
			return rt;
		}
		int rt=++cnt;
		xp[rt]=a;
		Add(tmp,(LL)val[ls[x]]*val[rs[y]]%mod*ival[a]%mod*ival[a/2]%mod);
		Add(tmp,(LL)val[rs[x]]*val[ls[y]]%mod*ival[a]%mod*ival[a/2]%mod);
		val[rt]=Add(val[x]+val[y]);
		ls[rt]=merge(ls[x],ls[y],a*2);
		rs[rt]=merge(rs[x],rs[y],a*2+1);
		return rt;
	}
}
int p[N];
void dfs(int x,int v){
	v=(LL)v*x%mod;
	val[x]=v;
	ival[x]=Pow(v,mod-2);
	if (x>=(1<<n)){
		lp[x]=rp[x]=x;
	}
	else {
		int l=x*2,r=l+1;
		dfs(l,v);
		dfs(r,v);
		lp[x]=lp[l];
		rp[x]=rp[r];
	}
}
int rt[N];
void solve(int x){
	if (x>=(1<<n)){
		rt[x]=seg::ins(rt[x],1,p[x],(LL)val[x]*val[p[x]]%mod);
		return;
	}
	int l=x*2,r=l+1;
	solve(l);
	solve(r);
	tmp=0;
	rt[x]=seg::merge(rt[l],rt[r],1);
	Add(ans,(LL)tmp*ival[x/2]%mod*ival[x]%mod);
}
int main(){
	n=read()-1;
	s=(1<<(n+1))-1;
	val[0]=ival[0]=1;
	dfs(1,1);
//	outarr(val,1,s);
//	outarr(ival,1,s);
	For(i,(1<<n),s)
		p[i]=read()+(1<<n)-1;
	solve(1);
	cout<<ans<<endl;
	return 0;
}