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<cstdio>
#include<algorithm>
using namespace std;
int ans=0,sum=0,pp[262144],dp[262144],m,h,n,tr[5000005],cnt=0,hd[262144];
int ch[2][5000005];
const int mod=1e9+7;
int pos,v,rt,inv[262144];
int M(int x){return x>=mod?x-mod:x;}
int mypow(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1)ans=1ll*ans*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return ans;
}
void ins(int p,int l,int r)
{
	tr[p]=M(tr[p]+v);
	//printf("%d %d\n",tr[p],p);
	if(l==r)return;
	int mid=(l+r)/2;
	if(pos<=mid)ch[0][p]=++cnt,ins(cnt,l,mid);
	else ch[1][p]=++cnt,ins(cnt,mid+1,r);
}
int mrg(int x,int y,int p,int l,int r)
{
	//printf("#%d %d %d %d %d %d %d %d %d\n",x,y,p,inv[p],r,tr[ch[0][x]],tr[ch[1][y]],tr[3],tr[4]);
	if(x==0||y==0)return x+y;
	tr[x]=M(tr[x]+tr[y]);
	sum=(1ll*sum+1ll*tr[ch[0][x]]*tr[ch[1][y]]%mod*inv[p])%mod;
	sum=(1ll*sum+1ll*tr[ch[1][x]]*tr[ch[0][y]]%mod*inv[p])%mod;
	//printf("%d\n",sum);
	int mid=(l+r)/2;
	ch[0][x]=mrg(ch[0][x],ch[0][y],2*p,l,mid);
	ch[1][x]=mrg(ch[1][x],ch[1][y],2*p+1,mid+1,r);
	return x;
}
void dfs(int p)
{
	if(2*p>n)
	{
		hd[p]=++cnt;
		pos=pp[p]-m+1;
		v=1ll*dp[p]*dp[pp[p]]%mod;
		ins(hd[p],1,m);
		return;
	}
	else
	{
		dfs(2*p);
		dfs(2*p+1);
	}
	sum=0;rt=p;
	hd[p]=mrg(hd[2*p],hd[2*p+1],1,1,m);
	ans=(1ll*ans+1ll*sum*inv[p])%mod;
}
int main()
{
	scanf("%d",&h);
	n=(1<<h)-1;m=(1<<(h-1));
	dp[1]=1;inv[1]=1;
	for(int i=2;i<=n;i++)dp[i]=1ll*dp[i/2]*i%mod,inv[i]=mypow(dp[i],mod-2),inv[i]=1ll*inv[i]*inv[i]%mod*i%mod;
	for(int i=m;i<=n;i++)
	{
		scanf("%d",&pp[i]);
		pp[i]=m+pp[i]-1;
	}
	dfs(1);
	printf("%d\n",ans);
	return 0;
}