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 For(i,x,y) for (register int i=(x);i<=(y);i++)
#define FOR(i,x,y) for (register int i=(x);i<(y);i++)
#define Dow(i,x,y) for (register int i=(x);i>=(y);i--)
#define Debug(v) for (auto i:v) printf("%lld ",i);puts("")
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define ep emplace_back
#define siz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define fil(a,b) memset((a),(b),sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pa;
typedef pair<ll,ll> PA;
typedef vector<int> poly;
inline ll read(){
    ll x=0,f=1;char c=getchar();
    while ((c<'0'||c>'9')&&(c!='-')) c=getchar();
    if (c=='-') f=-1,c=getchar();
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}

const int N = 1<<18|3, mod = 1e9+7;
int h,cnt,n,p[N];

inline int power(int a,int b){
	int ret=1;
	for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) ret=1ll*ret*a%mod;
	return ret; 
}
inline int Mod(int x){
	return x>=mod?x-mod:x;
}

int Tim,l[N],r[N],f[N],invf[N],inv[N];
poly v[N];
inline void dfs(int u){
	invf[u]=power(f[u],mod-2);
	if (p[u]) return l[u]=r[u]=u,void(0);
	f[u<<1]=1ll*f[u]*(u<<1)%mod;
	f[u<<1^1]=1ll*f[u]*(u<<1^1)%mod;
	dfs(u<<1),dfs(u<<1^1);
	l[u]=l[u<<1],r[u]=r[u<<1^1];
}
int ans,flag[N],ip[N];
inline void dfs2(int u){
	if (p[u]) return v[u].pb(p[u]+cnt-1),void(0);
	dfs2(u<<1),dfs2(u<<1^1);
	v[u]=v[u<<1];
	for (auto i:v[u<<1^1]) v[u].pb(i);
//	printf(" %d:\n",u);
//	for (auto i:v[u]) printf("%d ",i);puts("");
	for (auto i:v[u<<1]){
		int tmp=1ll*f[ip[i]]*invf[u]%mod*u%mod;
		for (int now=i;now;now>>=1){
			tmp=1ll*tmp*now%mod,flag[now]=Mod(flag[now]+tmp);
		}
	}
	for (auto i:v[u<<1^1]){
		int tmp=1ll*f[ip[i]]*invf[u]%mod,tmp2=i;
		for (int las=i,now=i>>1;now;las=now,now>>=1){
			tmp2=1ll*tmp2*now%mod;
			if (now*2==las){
				ans=(ans+1ll*flag[now*2+1]*tmp%mod*tmp2)%mod;
			} else {
				ans=(ans+1ll*flag[now*2]*tmp%mod*tmp2)%mod;
			}
		}
	}
	for (auto i:v[u<<1])
		for (int now=i;now;now>>=1) flag[now]=0;
}

int main(){
	h=read(),cnt=1<<(h-1),n=cnt*2-1;
	For(i,1,cnt) p[cnt+i-1]=read(),ip[p[cnt+i-1]+cnt-1]=cnt+i-1;
	For(i,1,n) inv[i]=power(i,mod-2);
	f[1]=invf[1]=1,dfs(1),dfs2(1),printf("%d\n",ans);
}