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 ls (now*2)
#define rs (now*2+1)
#define ll long long
using namespace std;
const ll H=18;
const ll N=(1<<H)+5;
const ll mod=1e9+7;

ll read()
{
	ll s=0;
	char c=getchar(),lc='+';
	while (c<'0'||'9'<c) lc=c,c=getchar();
	while ('0'<=c&&c<='9') s=s*10+c-'0',c=getchar();
	return lc=='-'?-s:s;
}
void write(ll x)
{
	if (x<0)
	{
		putchar('-');
		x=-x;
	}
	if (x<10) putchar(x+'0');
	else
	{
		write(x/10);
		putchar(x%10+'0');
	}
}
void print(ll x,char c='\n')
{
	write(x);
	putchar(c);
}
ll p[N],h,l,a[N],v[N],cnt,ans=0;
void dfs1(ll now,ll deep,ll mul)
{
	mul=mul*now%mod;
	if (deep==h)
	{
		ll i=now-l+1;
		now=l+p[i]-1;
		v[++cnt]=now;
		while (now)
		{
			mul=mul*now%mod;
			a[now]=(a[now]+mul)%mod;
			now/=2;
		}
		return;
	}
	dfs1(ls,deep+1,mul);
	dfs1(rs,deep+1,mul);
}
void dfs2(ll now,ll deep,ll mul)
{
	mul=mul*now%mod;
	if (deep==h)
	{
		ll i=now-l+1;
		now=l+p[i]-1;
		mul=mul*now%mod;
		while (now>1)
		{
			mul=mul*(now/2)%mod;
			ans=(ans+mul*a[now^1]%mod)%mod;
			now/=2;
		}
		return;
	}
	dfs2(ls,deep+1,mul);
	dfs2(rs,deep+1,mul);
}
void solve(ll now,ll deep)
{
	cnt=0;
	dfs1(ls,deep+1,now);
//	print(now);
//	for (int i=1;i<=7;i++) print(a[i],' ');
//	puts("");
	dfs2(rs,deep+1,1);
	for (ll i=1;i<=cnt;i++)
	{
		ll w=v[i];
		while (w)
		{
			a[w]=0;
			w/=2;
		}
	}
}
void dfs0(ll now,ll deep)
{
	if (deep==h) return;
	solve(now,deep);
	dfs0(ls,deep+1);
	dfs0(rs,deep+1);
}

int main()
{
	memset(a,0,sizeof(a));
	h=read();
	l=1<<(h-1);
	for (ll i=1;i<=l;i++) p[i]=read();
	dfs0(1,1);
	print(ans);

	return 0;
}