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(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
cs int Mod = 1e9 + 7;
int add(int a, int b){ return a + b >= Mod ? a + b - Mod : a + b; }
int dec(int a, int b){ return a - b < 0 ? a - b + Mod : a - b; }
int mul(int a, int b){ return 1ll * a * b % Mod; }
void Add(int &a, int b){ a = add(a, b); }
void Dec(int &a, int b){ a = dec(a, b); }
void Mul(int &a, int b){ a = mul(a, b); }
int ksm(int a, int b){ 
	int ans = 1; for(;b;b>>=1, Mul(a, a))
	if(b & 1) Mul(ans, a); return ans;
}
cs int N = 1 << 18 | 5;
int H, n, l[N], r[N], p[N], vl[N], iv[N], rt[N];
namespace pst{
	#define mid ((l+r) >> 1)
	cs int N = ::N * 20;
	int lc[N], rc[N], vl[N], nd;
	int copy(int u){ int x = ++nd; lc[x] = lc[u], rc[x] = rc[u], vl[x] = vl[u]; return x; }
	void ins(int &x, int l, int r, int p, int v){
		x = copy(x); Add(vl[x], v); if(l == r) return;
		if(p <= mid) ins(lc[x], l, mid, p, v);
		else ins(rc[x], mid + 1, r, p, v); 
	} int ask(int a, int b, int l, int r, int L, int R){
		if(!a) return 0; if(L <= l && r <= R) return dec(vl[a], vl[b]);
		int ans = 0; if(L <= mid) Add(ans, ask(lc[a], lc[b], l, mid, L, R));
		if(R > mid) Add(ans, ask(rc[a], rc[b], mid + 1, r, L, R)); return ans;
	}
} 
void build(int x, int l, int r){
	::l[x] = l, ::r[x] = r;
	if(l == r) return; 
	build(x << 1, l,  mid);
	build(x << 1 | 1, mid + 1, r);
}
int main(){
	#ifdef FSYolanda
	freopen("1.in","r",stdin);
	#endif
	scanf("%d", &H); n = 1 << (H - 1);
	for(int i = 1; i <= n; i++) scanf("%d", &p[i]);
	build(1, 1, n);
	for(int i = 1; i < n + n; i++){
		vl[i] = 1; for(int x = i; x; x >>= 1)
		Mul(vl[i], x); iv[i] = ksm(vl[i], Mod - 2);
	}
	for(int i = 1; i <= n; i++)
	rt[i] = rt[i - 1], pst :: ins(rt[i], 1, n, p[i], mul(vl[p[i] + n - 1], vl[i + n - 1]));
	int ans = 0; vl[0] = iv[0] = 1;
	for(int i = 1; i <= n; i++){
		int coe = mul(vl[p[i] + n - 1], vl[i + n - 1]);
		for(int x = i + n - 1; x > 1; x >>= 1)
		for(int y = p[i] + n - 1; y > 1; y >>= 1){
			int c = pst :: ask(rt[r[x ^ 1]], rt[l[x ^ 1] - 1], 1, n, l[y ^ 1], r[y ^ 1]);
			Add(ans, mul(mul(c, coe), mul(mul(iv[x >> 1], iv[x >> 2]), mul(iv[y >> 1], iv[y >> 2]))));
		}
	} cout << mul(ans, (Mod + 1) >> 1); return 0;
}