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;
#define endl '\n'
#define all(x) (x).begin(),(x).end()
const int INF=1e9+5;
const int N=3e5+5;
const int mod=1e9+7;

int product[18][1<<18];
int a[1<<18];

vector<pair<int,int>> v[N];
int maps[1<<18];

void add(int par2,int par1,int val){
	if(v[par2].empty()||v[par2].back().first<par1) v[par2].emplace_back(par1,val);
	else{
		v[par2].back().second+=val;
		//~ cout<<par2<<" ~~ "<<par1<<endl;
		if(v[par2].back().second>=mod) v[par2].back().second-=mod;
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int k;
	cin>>k;
	int L=1<<(k-1);
	for(int i=L;i<L+L;++i){
		product[0][i]=i;
		for(int j=1;j<k;++j){
			product[j][i]=(1ll*product[j-1][i]*(i>>j))%mod;
		}
	}
	for(int i=L;i<L+L;++i){
		int x;
		cin>>x;
		a[i]=x+L-1;
	}
	for(int k1=k-1;k1>=0;--k1){
		for(int k2=k-1;k2>=0;--k2){
			for(int i=L;i<L+L;++i){
				int op=a[i];
				int prod=(1ll*product[k1][i]*product[k2][op])%mod;
				int par1=(i>>k1),par2=(op>>k2);
				add(par2,par1,prod);
			}
		}
	}
	//~ for(int i=0;i<L;++i){
		//~ for(pair<int,int> x:v[i]) cout<<x.first<<" ";
		//~ cout<<endl;
	//~ }
	ll ans=0;
	for(int i=1;i<=L;++i){
		int left=i*2;
		int right=i*2+1;
		for(pair<int,int> x:v[right]) maps[x.first]=x.second;
		for(pair<int,int> x:v[left]){
			int num=x.first;
			if(num==1) continue;
			unsigned long long val=(1ll*x.second*maps[num^1])%mod;
			val=(val*i*(num>>1))%mod;
			ans+=val;
		}
		for(pair<int,int> x:v[right]) maps[x.first]=0;
	}
	cout<<ans%mod;
	return 0;
}	
