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;

#define ll long long
#define ar array

const int mxH=18, mxN=1<<mxH, M=1e9+7;
int h, n, a[mxN/2], fl[mxN], fr[mxN];
ll ans, iv[mxN], w[mxN];

void dfs1(int u=1, int p=0) {
	if(p)
		w[u]=w[p]*u%M;
	else
		w[u]=1;
	fl[u]=fr[u]=u;
	while(fl[u]<n/2) {
		fl[u]=fl[u]*2;
		fr[u]=fr[u]*2+1;
	}
	if(u<n/2) {
		dfs1(2*u, u);
		dfs1(2*u+1, u);
	}
}

vector<ar<int, 2>> lv;

ll dfs3(int l1, int r1, int u=1, int p=0, ll fix=1) {
	if(u>=n/2||l1>=r1)
		return 0;
	ll fix2=fix*(1+M-(ll)u*p%M)%M, ans=0, s=0;
	for(int i=l1; i<r1; ++i) {
		ans=(ans+w[lv[i][0]+n/2]*w[lv[i][1]+n/2]%M*s)%M;
		s=(s+w[lv[i][0]+n/2]*w[lv[i][1]+n/2])%M;
	}
	ans=ans*fix2%M;
	int m1=l1;
	while(m1<r1&&lv[m1][0]<=fr[2*u]-n/2)
		++m1;
	ans+=dfs3(l1, m1, 2*u, u, fix*iv[2*u]%M*iv[u]%M);
	ans+=dfs3(m1, r1, 2*u+1, u, fix*iv[2*u+1]%M*iv[u]%M);
	return ans%M;
}

void dfs2(int u=1, int p=0, ll fix=1) {
	if(u>=n/2)
		return;
	ll fix2=fix*(1+M-(ll)u*p%M)%M;
	//(a[i], i) for i in [fl[u], fr[u]]-n/2
	for(int i=fl[u]-n/2; i<=fr[u]-n/2; ++i)
		lv.push_back({a[i], i});
	sort(lv.begin(), lv.end());
	ans=(ans+fix2*dfs3(0, lv.size()))%M;
	lv.clear();
	dfs2(2*u, u, fix*iv[2*u]%M*iv[u]%M);
	dfs2(2*u+1, u, fix*iv[2*u+1]%M*iv[u]%M);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> h;
	n=1<<h;
	for(int i=0; i<n/2; ++i)
		cin >> a[i], --a[i];
	iv[1]=1;
	for(int i=2; i<n; ++i)
		iv[i]=M-M/i*iv[M%i]%M;
	dfs1();
	dfs2();
	cout << ans;
}