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 <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<ctime>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<bitset>
#define sqr(x) ((x)*(x))
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define fd1(i,n) for ((i)=(n);(i)>=1;(i)--)
#define fz0g(i,n) for ((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for ((i)=(n);(i)>=0;(i)--)
#define fz0k(i,n) for ((i)=0;(i)<(n);(i)++)
#define fd0k(i,n) for ((i)=(long long)((n)-1);(i)>=0;(i)--)
#define fz(i,x,y) for ((i)=(x);(i)<=(y);(i)++)
#define fd(i,y,x) for ((i)=(y);(i)>=(x);(i)--)
#define fzin fz1(i,n)
#define fzim fz1(i,m)
#define fzjn fz1(j,n)
#define fzjm fz1(j,m)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();++itr)
#define rdst(st,len){static char ss[len];scanf(" %s",ss);(st)=ss;}
#define inc(x,y) {x+=(y);if(x>=mod)x-=mod;}
#define dec(x,y) {x-=(y);if(x<0)x+=mod;}
#define incm(x,y) {x=((x)+(y))%mod;}
#define spln(i,n) (i==n?'\n':' ')
#define fac_init(n){fac[0]=fac[1]=inv[1]=fi[0]=fi[1]=1;fz(i,2,n){fac[i]=1ll*fac[i-1]*i%mod;inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;fi[i]=1ll*fi[i-1]*inv[i]%mod;}}
using namespace std;
inline void read(int &x)
{
	char c;int f=1;
	while(!isdigit(c=getchar()))if(c=='-')f=-1;
	x=(c&15);while(isdigit(c=getchar()))x=(x<<1)+(x<<3)+(c&15);
	x*=f;
}
const int mod=1e9+7;
int n,m,i,j,a[300005],flk[300005],fa[300005],dep[300005],dfn[300005],ti2,fi[300005],ed[300005],ti,pro[300005],res[300005],ans,mp[300005];
int vis[300005],stk[300005],tp,dp[300005];
vector<int> bi[300005],all,bi2[300005];
void add(int x,int y)
{
//	cerr<<x<<' '<<y<<endl;
	bi2[x].push_back(y);
}
int qp(int x,int y)
{
	int z=1;
	while(y){
		if(y&1) z=1ll*z*x%mod;
		x=1ll*x*x%mod;y/=2;
	}
	return z;
}
void dfs1(int x)
{
	fi[x]=ti+1;dfn[x]=++ti2;
	if(x>=(1<<(n-1))) mp[++ti]=x;
	ff(bi[x],it){
		dep[*it]=dep[x]+1;
		pro[*it]=1ll*pro[x]*(*it)%mod;
		dfs1(*it);
	}
	ed[x]=ti;
}
void dfs2(int x)
{
	dp[x]=(x>=(1<<(n-1))?1ll*pro[x]*pro[flk[x]]%mod:0);
	ff(bi2[x],it){
		dfs2(*it);
		res[i]=(res[i]+1ll*dp[x]*dp[*it]%mod*qp(pro[x],mod-2)%mod*qp(pro[fa[x]],mod-2))%mod;
		dp[x]=(dp[x]+dp[*it])%mod;
	}
}
int lca(int x,int y)
{
	while(x!=y){
		x>>=1;y>>=1;
	}
	return x;
}
void ins(int x)
{
	if(tp<=1){
		stk[++tp]=x;
		return;
	}
	int z=lca(x,stk[tp]);
	if(z==stk[tp]){
		stk[++tp]=x;
		return;
	}
	while(tp>1&&dfn[stk[tp-1]]>=dfn[z]){
		add(stk[tp-1],stk[tp]);
		tp--;
	}
	if(stk[tp]!=z){
		add(z,stk[tp]);
		stk[tp]=z;
		all.push_back(z);
	}
	stk[++tp]=x;
}
int main()
{
	read(n);
	fz1(i,(1<<(n-1))-1){
		bi[i].push_back(i*2);
		bi[i].push_back(i*2+1);
		fa[i*2]=i;
		fa[i*2+1]=i;
	}
	pro[1]=pro[0]=1;
	dfs1(1);
	fz1(i,(1<<(n-1))){
		read(a[i]);
		flk[a[i]+(1<<(n-1))-1]=i+(1<<(n-1))-1;
	}
	fz1(i,(1<<(n-1))-1){
		vector<int> v;all.clear();all.push_back(1);
		fz(j,fi[i],ed[i]){
			v.push_back(mp[a[j]]);
			all.push_back(mp[a[j]]);
		}
		sort(v.begin(),v.end());
		ff(v,it) vis[*it]=1;
		stk[tp=1]=1;
		ff(v,it){
			ins(*it);
		}
		while(tp>1){
			add(stk[tp-1],stk[tp]);
			tp--;
		}
		dfs2(1);
		ff(v,it) vis[*it]=0;
		ff(all,it) bi2[*it].clear();
	}
	fz1(i,(1<<(n-1))-1){
		ans=(ans+1ll*qp(pro[i],mod-2)*qp(pro[fa[i]],mod-2)%mod*((0ll+res[i]-res[i*2]-res[i*2+1]+mod+mod)%mod))%mod;
	}
	cout<<ans<<endl;
	return 0;
}