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>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=(1<<18)+5;
const int mod=1e9+7;
int H,n,p[maxn],dep[maxn];
ll inv[maxn],S[maxn],invS[maxn],w[maxn][2],ans,res;
vector<int> g[maxn];
#define ls (rt<<1)
#define rs (rt<<1|1)
void init(int rt,int l,int r)
{
//	cout<<rt<<' '<<S[rt]<<' '<<invS[rt]<<endl;
	if(l==r) return;
	int mid=(l+r)>>1;
	dep[ls]=dep[rs]=dep[rt]+1;
	S[ls]=S[rt]*ls%mod;
	invS[ls]=invS[rt]*inv[ls]%mod;
	S[rs]=S[rt]*rs%mod;
	invS[rs]=invS[rt]*inv[rs]%mod;
	init(ls,l,mid),init(rs,mid+1,r);
}
inline int LCA(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	while(dep[x]>dep[y]) x>>=1;
	if(x==y) return x;
	while(x!=y) x>>=1,y>>=1;
	return x;
}
void clear(int x)
{
	for(auto y:g[x]) clear(y);
	w[x][0]=w[x][1]=0,g[x].clear();
}
void dfs(int x)
{
	ll val=0;
	for(auto y:g[x])
	{
		dfs(y);
		(val+=w[x][0]*w[y][1]+w[x][1]*w[y][0])%=mod;
		(w[x][0]+=w[y][0])%=mod,(w[x][1]+=w[y][1])%=mod;
	}
	(res+=val*invS[x]%mod*invS[x>>1])%=mod;
}
inline void addedge(int x,int y) { g[x].push_back(y); }
void solve(int rt,int l,int r)
{
	if(l==r) return;
	int mid=(l+r)>>1;
	solve(ls,l,mid),solve(rs,mid+1,r);
//	printf("solve %d %d %d %lld\n",rt,l,r,S[rt]);
	for(int i=l;i<=mid;i++) w[p[i]+n-1][0]=S[i+n-1]*S[p[i]+n-1]%mod;
	for(int i=mid+1;i<=r;i++) w[p[i]+n-1][1]=S[i+n-1]*S[p[i]+n-1]%mod;
	static int h[maxn],sta[maxn],top;
	for(int i=l;i<=r;i++) h[i-l+1]=p[i]+n-1;
	int len=r-l+1;
	sort(h+1,h+len+1);
	sta[top=1]=1;
	for(int i=1;i<=len;i++)
	{
		int lca=LCA(sta[top],h[i]);
		while(dep[lca]<dep[sta[top]])
		{
			if(dep[sta[top-1]]<=dep[lca])
			{
				addedge(lca,sta[top]);
				if(sta[--top]!=lca) sta[++top]=lca;
				break;
			}
			addedge(sta[top-1],sta[top]);top--;
		}
		if(sta[top]!=h[i]) sta[++top]=h[i];
	}
	while(--top) addedge(sta[top],sta[top+1]);
	res=0,dfs(1),(ans+=res*invS[rt]%mod*invS[rt>>1])%=mod,clear(1);
}
int main()
{
	inv[0]=inv[1]=1;
	for(int i=2;i<maxn;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	scanf("%d",&H); n=(1<<(H-1));
	for(int i=1;i<=n;i++) scanf("%d",&p[i]);
	dep[1]=1,S[0]=invS[0]=S[1]=invS[1]=1ll,init(1,1,n),solve(1,1,n);
	printf("%lld\n",ans);
	return 0;
}