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 pair < int , int > pii;
#define mpr make_pair
#define FS first
#define SC second
#define PB push_back
template < typename T > T MAX(T a,T b){return (a>b)?a:b;}
template < typename T > T MIN(T a,T b){return (a<b)?a:b;}
template < typename T > void UMAX(T &a,T b){a=(a>b?a:b);}
template < typename T > void UMIN(T &a,T b){a=(a<b?a:b);}
LL readint(){
	char c=getchar();
	LL ret=0ll;
	bool neg=0;
	while(!(c>='0' && c<='9')){
		if(c=='-') neg=1;
		c=getchar();
	}
	while(c>='0' && c<='9'){
		ret=ret*10ll+(LL)(c-'0');
		c=getchar();
	}
	return neg?-ret:ret;
}
void putint(LL v){
	if(v<0){
		putchar('-');
		v=-v;
	}
	if(!v){
		putchar('0');
		return;
	}
	if(v>=10ll) putint(v/10ll);
	putchar('0'+(v%10ll));
}
const int MOD=1000000007;
int powM(int V,int T=MOD-2){
	int R=1;
	while(T){
		if(T&1) R=(LL)R*V%MOD;
		T>>=1;
		V=(LL)V*V%MOD;
	}
	return R;
}
int H,sum[300005],tag[300005],prd[300005],adt[300005],p[300005];
void add(int d,int t,int v){
	if(tag[d]!=t){
		sum[d]=0;
		tag[d]=t;
	}
	sum[d]+=v;
	if(sum[d]>=MOD) sum[d]-=MOD;
}
#define initialization_confirm
#define corner_case_check
#define return_type_of_template_and_operator
int main(){
	#ifdef LOCAL_QTY
		#ifndef initialization_confirm // 不要忘记初始化
			exit(0);
		#endif
		#ifndef corner_case_check // 不要忘记检查边界情况（图不连通，n=1，etc.）
			exit(0);
		#endif
		#ifndef return_type_of_template_and_operator // 勿忘返回值类型
			exit(0);
		#endif
	#endif
	int i,j,k;
	H=readint();
	prd[0]=1;
	for(i=1;i<(1<<H);++i){
		prd[i]=prd[i>>1]*(LL)i%MOD;
	}
	for(i=(1<<H)-1;i>=1;--i){
		adt[i]=powM((LL)prd[i>>1]*prd[i>>1]%MOD*i%MOD);
	}
	for(i=(1<<H)-1;i>=1;--i){
		if(i>1){
			adt[i]-=adt[i>>1];
			if(adt[i]<0) adt[i]+=MOD;
		}
	}
	int res=0;
	for(i=(1<<(H-1));i<(1<<H);++i){
		p[i]=readint()+(1<<(H-1))-1;
		int cp=(LL)prd[i]*prd[p[i]]%MOD;
		cp=(LL)cp*cp%MOD;
		for(j=i>>1;j;j>>=1){
			for(k=p[i]>>1;k;k>>=1){
				res-=(LL)cp*adt[j]%MOD*adt[k]%MOD;
				if(res<0) res+=MOD;
			}
		}
	}
	memset(tag,-1,sizeof(tag));
	for(i=(1<<(H-1))-1;i>=1;--i){
		int l=i,r=i+1;
		while(l<(1<<(H-1))) l<<=1,r<<=1;
		--r;
		vector < int > ps;
		for(j=l;j<=r;++j){
			ps.push_back(p[j]);
			for(k=p[j]>>1;k>=1;k>>=1){
				add(k,i,(LL)prd[p[j]]*prd[j]%MOD);
			}
		}
		for(j=0;j<(int)ps.size();++j){
			int d=ps[j];
			for(k=d>>1;k>=1;k>>=1){
				if(tag[k]!=i) continue;
				res+=(LL)sum[k]*sum[k]%MOD*adt[i]%MOD*adt[k]%MOD;
				if(res>=MOD) res-=MOD;
				tag[k]=-1;
			}
		}
	}
	printf("%lld\n",(LL)res*powM(2)%MOD);
	return 0;
}
/*
 * 代码框架
 * 1. 开一个数组，预处理每个标号对应的到根的链乘积；以及在每个 lca处应该额外乘上的值
 * 		对于lca权值预先做差分，从而不用再考虑重复
 * 2. 自底向上枚举第一棵树上的结点，暴力枚举其中的点在对面的外联边，记录次数
 * 		开数组记录每个对面结点子树内链的条数，开数组记录每个对面结点是否访问过
 * 		每次自底向上枚举对面结点，计算与它的贡献。
*/