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
/*
*/

#pragma GCC optimize("O3")
#define _CRT_SECURE_NO_WARNINGS
#include <assert.h>
#include <math.h>
#include <memory.h>
#include <stdio.h>

#include <algorithm>
#include <complex>
#include <ctime>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define y0 sdkfaslhagaklsldk

#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define left asdgashgrketwjklrej
#define have adsgagshdshfhds
#define ends asdgahhfdsfshdshfd
#define prev asdgSHJsfgsdfhdsh
#define hash asdgasdgasdgdfrywewery

#define eps 1e-12
#define M_PI 3.141592653589793
#define bsize 1024

#define ldouble long double
using namespace std;

#define bs 1000000007

const int N = 300031;

int H,P[N];
long long ans;
int dep[N];
long long prod_up[N][20];
long long sum_left[N],sum_right[N];
long long last_processed_root[N];
queue<int> qu;

void magic(int v,int root){
	if (last_processed_root[v*2]!=root){
		sum_left[v*2]=sum_right[v*2]=0;
	}
	if (last_processed_root[v*2+1]!=root){
		sum_left[v*2+1]=sum_right[v*2+1]=0;
	}
}
void solver(long long root){
	int block=(1<<(H-dep[root]))/2;
	/*for (int i=1;i<=(1<<H);i++){
		sum_left[i]=sum_right[i]=0;
	}*/

	// left
	int start=root*(1<<(H-dep[root]));
	int finish=start+block-1;
	for (int i=start;i<=finish;i++){
		int to=P[i];
		sum_left[to]=sum_right[to]=0;
		sum_left[to]=prod_up[i][H-dep[root]]*to%bs;
		sum_left[to]%=bs;
		qu.push(to);
		last_processed_root[to]=root;
	}

	// to do left
	start=finish+1;
	finish=start+block-1;
	for (int i=start;i<=finish;i++){
		int to=P[i];
		sum_left[to]=sum_right[to]=0;
		sum_right[to]=prod_up[i][H-dep[root]]*to%bs;
		qu.push(to);
		last_processed_root[to]=root;
	}

	/*for (int i=(1<<H)-1;i>=1;--i){
		int v=i;
		if (v<(1<<(H-1))){
			cout<<v<<" "<<sum_left[v*2]<<" "<<sum_right[v*2+1]<<" "<<root<<endl;
			ans+=sum_left[v*2]*sum_right[v*2+1]%bs*v%bs*root%bs;
			ans+=sum_right[v*2]*sum_left[v*2+1]%bs*v%bs*root%bs;
			ans%=bs;
		}
		int parent=v/2;
		if (parent==0)
			continue;
		sum_left[parent]+=sum_left[v]*parent%bs;
		sum_right[parent]+=sum_right[v]*parent%bs;
		sum_left[parent]%=bs;
		sum_right[parent]%=bs;
	}
*/
	while (qu.size()){
		int v=qu.front();
		qu.pop();
		if (v<(1<<(H-1))){
			magic(v,root);
			//cout<<v<<" "<<sum_left[v*2]<<" "<<sum_right[v*2+1]<<" "<<root<<endl;
			ans+=sum_left[v*2]*sum_right[v*2+1]%bs*v%bs*root%bs;
			ans+=sum_right[v*2]*sum_left[v*2+1]%bs*v%bs*root%bs;
			ans%=bs;
		}
		int parent=v/2;
		if (parent==0)
			continue;
		if (last_processed_root[parent]!=root){
			sum_left[parent]=0;
			sum_right[parent]=0;
			last_processed_root[parent]=root;
			qu.push(parent);
		}
		sum_left[parent]+=sum_left[v]*parent%bs;
		sum_right[parent]+=sum_right[v]*parent%bs;
		sum_left[parent]%=bs;
		sum_right[parent]%=bs;
	}

}

int main() {
   //freopen("input.txt", "r", stdin);
   //freopen("output.txt", "w", stdout);
  ios_base::sync_with_stdio(0);
  // cin.tie(0);

  dep[1]=1;
  for (int i=2;i<N;i++){
	  dep[i]=dep[i/2]+1;
  }

  for (int i=1;i<N;i++){
	  prod_up[i][0]=1;
	  for (int len=1;len<=dep[i];len++){
		prod_up[i][len]=prod_up[i][len-1]*(i/(1<<(len-1)));
		prod_up[i][len]%=bs;
	  }
  }

  cin>>H;
  for (int i=(1<<(H-1));i<(1<<H);i++){
	  cin>>P[i];
	  P[i]+=(1<<(H-1))-1;
  }

  for (int root=(1<<H)-1;root>=1;root--){
	 solver(root);
  }

  cout<<ans<<endl;

  cin.get(); cin.get();
  return 0;
}
