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>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> pi3;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int N=18;

ll n, nn, k, u, v, x, y, a, b, ans;
ll A[1<<N];
int sz[4];
pi3 B[4][N*N<<N>>3];
pii C[4][N*N<<N>>3];
int L[4][1<<N], R[4][1<<N], ted[4][1<<N];
int sum[4][1<<N];

inline void fix(int &x){
	if (x>=mod) x-=mod;
	if (x<0) x+=mod;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n; nn=(1<<(n-1));
	for (int i=0; i<nn; i++){
		cin>>A[i];
		int u=i+nn, v=A[i]+nn-1;
		ll mul=1;
		while (u>1){
			mul=mul*u%mod;
			int vv=v;
			ll mul2=mul;
			while (vv>1){
				mul2=mul2*vv%mod;
				int tmp=((u&1)<<1)|(vv&1);
				B[tmp][sz[tmp]++]={{u>>1, vv>>1}, mul2};
//				cerr<<"path "<<(u>>1)<<' '<<(vv>>1)<<' '<<tmp<<" "<<mul2<<"\n";
				ted[tmp][u>>1]++;
				vv>>=1;
			}
			u>>=1;
		}
	}
	for (int tmp:{0, 1, 2, 3}){
		for (int i=1; i<(1<<n); i++) L[tmp][i]=R[tmp][i]=L[tmp][i-1]+ted[tmp][i-1];
	}
	for (int tmp:{0, 1, 2, 3}){
		for (int i=0; i<sz[tmp]; i++){
			int u=B[tmp][i].first.first, v=B[tmp][i].first.second, mul=B[tmp][i].second;
			C[tmp][R[tmp][u]++]={v, mul};
		}
	}
	for (int u=1; u<(1<<n); u++){
		for (int tmp:{0, 1, 2, 3}){
			for (int i=L[tmp][u]; i<R[tmp][u]; i++){
				pii p=C[tmp][i];
				fix(sum[tmp][p.first]+=p.second);
			}
		}
		for (int tmp:{0, 1, 2, 3}){
			for (int i=L[tmp][u]; i<R[tmp][u]; i++){
				int v=C[tmp][i].first, mul=C[tmp][i].second;
//				cerr<<"cycle "<<u<<' '<<v<<' '<<tmp<<"  "<<mul<<' '<<sum[tmp^3][v]<<"\n";
				ans=(ans + 1ll*sum[tmp^3][v]*mul%mod*v%mod*u%mod)%mod;
			}
		}
		for (int tmp:{0, 1, 2, 3}){
			for (int i=L[tmp][u]; i<R[tmp][u]; i++){
				pii p=C[tmp][i];
				sum[tmp][p.first]=0;
			}
		}
		
	}
	ans%=mod;
	ans=ans*(mod+1)/2%mod;
	cout<<ans<<"\n";
	
	
	return 0;
}
