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 FOR(i, x, y) for(int i = (x); i < (y); ++i)
#define REP(i, x, y) for(int i = (x); i <= (y); ++i)
#define PB push_back
#define MP make_pair
#define PH push
#define fst first
#define snd second
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 1 << 19;
const int INF = 1e9 + 7;

inline void uadd(int &x, int y){ (x += y) %= INF; return; }
inline void umul(int &x, int y){ x = 1ll * x * y % INF; return; }
inline int mul(int x, int y){ return 1ll * x * y % INF; }

int n, h, ans;
int f[maxn], g[maxn], vis1[maxn], vis2[maxn], a[maxn], p[maxn], inv[maxn], dis[maxn];
vector<int> tmp1, tmp2;

inline int qpow(int x, int y){
	int res = 1;
	for(; y; y >>= 1){
		if(y & 1)
			umul(res, x);
		umul(x, x);
	}
	return res;
}

inline void dfs1(int u){
	if(u >= (1 << h - 1)){
		for(int v = p[u]; v; v >>= 1){
//			printf("u = %d v = %d\n", u, v);
			if(!vis1[v]){
				tmp1.PB(v);
				vis1[v] = true;
			} 
			uadd(f[v], a[u]);
		}
		return;
	}
	dfs1(u << 1);
	dfs1(u << 1 | 1);
	return;
}

inline void dfs2(int u){
	if(u >= (1 << h - 1)){
		for(int v = p[u]; v; v >>= 1){
			if(!vis2[v]){
				tmp2.PB(v);
				vis2[v] = true;
			}
			uadd(g[v], a[u]); 
		}
		return;
	}
	dfs2(u << 1);
	dfs2(u << 1 | 1);
	return;
}

int main(){
	scanf("%d", &h);
	FOR(i, 1 << h - 1, 1 << h){
		scanf("%d", p + i); p[i] += (1 << h - 1) - 1;
		a[i] = 1;
		for(int j = i; j; j >>= 1)
			umul(a[i], j);
		for(int j = p[i]; j; j >>= 1)
			umul(a[i], j);
	}
	
	dis[0] = 1;
	FOR(i, 1, 1 << h){
		inv[i] = qpow(i, INF - 2); 
		dis[i] = mul(inv[i], dis[i >> 1]);
	}
	
	FOR(i, 1, 1 << h - 1){
		dfs1(i << 1);
		dfs2(i << 1 | 1);
		FOR(j, 0, tmp1.size()){
			int r = tmp1[j];
			if(!(vis1[r] && vis2[r]))
				continue;
			if(r >= (1 << h - 1))
				continue;
			int res = 0;
			uadd(res, mul(f[r << 1], g[r << 1 | 1]));
			uadd(res, mul(f[r << 1 | 1], g[r << 1]));
			umul(res, dis[r]);
			if(r != 1)
				umul(res, dis[r >> 1]);
			umul(res, dis[i]);
			if(i != 1)
				umul(res, dis[i >> 1]);
			uadd(ans, res);
		}
		FOR(j, 0, tmp1.size()){
			int v = tmp1[j];
			vis1[v] = f[v] = 0;
		}
		FOR(j, 0, tmp2.size()){
			int v = tmp2[j];
			vis2[v] = g[v] = 0;
		}
		tmp1.clear(); tmp2.clear();
	}
	
	printf("%d\n", ans);
	return 0;
}
