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;
const int mod = 1e9+7;
inline int add(int a,int b){a+=b;return a>=mod?a-mod:a;}
inline int sub(int a,int b){a-=b;return a<0?a+mod:a;}
inline int mul(int a,int b){return 1ll*a*b%mod;}
inline int qpow(int a,int b){int ret=1;for(;b;b>>=1,a=mul(a,a))if(b&1)ret=mul(ret,a);return ret;}
/* math */
const int N = (1<<18)*18;
int ch[N][2], s[N], sum[N], prod[N], cnt;
int H;
int inv[1<<18];
inline void addtag(int x,int p){
	prod[x]=mul(prod[x], p);
	sum[x]=mul(sum[x],p);
}
inline void pd(int x){
	if(prod[x]!=1){
		for(int j=0;j<2;j++)if(ch[x][j]){
			addtag(ch[x][j], prod[x]);
		}
		prod[x]=1;
	}
}
inline void ins(int& rt,int s,int x,int dep,int curs){
	int c=(s>>(dep-1))&1;
	if(!rt){
		rt=++cnt;
		prod[rt] = 1, sum[rt] = 0;
	}
	// cout << x << "::" << curs << endl;
	pd(rt);
	if(!dep){
		sum[rt] = add(sum[rt], mul(x, s));
		prod[rt] = 1;
		return ;
	}
	ins(ch[rt][c],s,x,dep-1,curs*2+c);
	if(ch[rt][0])sum[rt] = add(sum[rt], sum[ch[rt][0]]);
	if(ch[rt][1])sum[rt] = add(sum[rt], sum[ch[rt][1]]);
	sum[rt] = mul(sum[rt], curs);
}
int ans2;
inline int merge(int x,int y,int s){
	if(!x||!y)return x+y;
	pd(x),pd(y);
	ch[x][0] = merge(ch[x][0], ch[y][0], s<<1), ch[x][1] = merge(ch[x][1], ch[y][1], s<<1|1);
	// cout << s << ":" << sum[x] << " " << sum[y] << ":" << endl;
	int qwq = mul(inv[s], mul(sum[x], sum[y]));
	// cout << qwq << endl;
	ans2 = add(ans2, qwq);
	ans2 = sub(ans2, mul(s/2,mul(sum[x],sum[y])));
	// cout << mul(s/2,mul(sum[x],sum[y])) << endl;
	sum[x] = add(sum[x], sum[y]);
	return x;
}

int p[1<<18];
int rt[1<<18];

int main()
{
	inv[1]=1;for(int i=2;i<1<<18;i++){
		inv[i] = mul(mod-mod/i,inv[mod%i]);
	}
	cin >> H;
	for(int i=0;i<1<<(H-1);i++){
		scanf("%d",&p[(1<<(H-1))+i]);
		p[(1<<(H-1))+i]--;
		p[(1<<(H-1))+i]+=1<<(H-1);
	}
	int ans=0;
	for(int i=(1<<H)-1;i;i--){
		if(i>=(1<<(H-1))){
			// cout << i << "->" << p[i] << "!" << endl;
			ins(rt[i], p[i], i, H-1, 1);
		}else{
			ans2=0;
			rt[i] = merge(rt[i<<1], rt[(i<<1)|1], 1);
			ans2 = mul(ans2, i);
			ans = add(ans, ans2);
			// cout << i << ">> ";cout << ans << ":" << ans2 << endl;
			addtag(rt[i], i);
		}
	}
	cout << ans << endl;
}