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 mod 1000000007
#define int long long
using namespace std;
const int N=(1<<19);
int n,m,a[N],fac[N],de[N],sum[N],ans;
int vi[N];
vector <int> p;
inline void add(int &a,int b){a=(a+b)%mod;}
inline void del(int &a,int b){a=(a-b+mod)%mod;}
inline void mul(int &a,int b){a=(a*b)%mod;}
inline int m_pow(int a,int b)
{
	int ans=1;
	while (b)
	{
		if (b&1) mul(ans,a);
		b>>=1;
		mul(a,a);
	}
	return ans;
}
void dfs(int x,int depth)
{
	de[x]=depth;
	if (x+x<(1<<n)) fac[x+x]=(fac[x]*(x+x))%mod,dfs(x+x,depth+1);
	if (x+x+1<(1<<n)) fac[x+x+1]=(fac[x]*(x+x+1))%mod,dfs(x+x+1,depth+1);
}
void change_path(int x,int v)
{
	mul(v,x);
	x/=2;
	while (x)
	{
		if (!vi[x]) p.push_back(x);
		vi[x]=1;
		mul(v,x);
		add(sum[x],v);
		x=x/2;
	}
}
void query(int x,int v)
{
	int last;
	mul(v,x);
	last=x;x/=2;
	while (x)
	{
		add(ans,v*(sum[x]-x*sum[last]%mod+mod)%mod);
		mul(v,x);
		last=x;
		x/=2;
	}
}
signed main()
{
	scanf("%lld",&n);m=(1<<(n-1));
	for (int i=1;i<=m;i++) scanf("%lld",&a[i]);
	fac[0]=fac[1]=1;
	dfs(1,1);
	for (int i=1;i<m;i++)
	{
		int full=(1<<(n-de[i]-1))-1;
		int x=(i<<1),div=m_pow(fac[i],mod-2);
		p.clear();
		for (int mask=0;mask<=full;mask++)
		{
			int now=((x<<(n-de[i]-1))|mask);
			change_path(a[now-m+1]+m-1,fac[now]*div%mod);
		}
		x=((i<<1)|1);
		div=m_pow(fac[i/2],mod-2);
		for (int mask=0;mask<=full;mask++)
		{
			int now=((x<<(n-de[i]-1))|mask);
			query(a[now-m+1]+m-1,fac[now]*div%mod); 
		} 
		for (int j=0;j<(int)p.size();j++) sum[p[j]]=vi[p[j]]=0;
	}
	printf("%lld\n",ans);
}