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>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define mid ((l + r) >> 1)
#define lch l, mid, o << 1
#define rch mid + 1, r, o << 1 | 1 

using namespace std;
const int N = (1 << 18) + 5, MI = 1e6, P = 1e9 + 7;
typedef long long ll;
int read() {
	static streambuf* in = cin.rdbuf();
	#define gc (p1 == p2 && (p2 = (p1 = buf) + in -> sgetn(buf, MI), p1 == p2) ? -1 : *p1++)
	static char buf[MI], *p1, *p2;
	int c = gc, r = 0;
	while(c < 48) c = gc;
	while(c > 47) r = (r << 3) + (r << 1) + (c & 15), c = gc;
	return r;
}
void wrt(int x) {
	static streambuf* out = cout.rdbuf();
	#define pc out -> sputc
	static char ch[11]; int sz = 0;
	if(!x) pc(48);
	else {
		while(x) ch[++sz] = x % 10, x /= 10;
		while(sz) pc(ch[sz--] + 48);
	} pc(10);
}
int h, l, p[N], bfn[N];
ll ans, w[N], sum[N];
void dfs(int l, int r, int o) {
	if(l == r) return bfn[l] = o, void();
	dfs(lch), dfs(rch);
}
void upd(int o, ll v) {
	for(; o; o >>= 1) sum[o] = (sum[o]+(v = v*o%P)) % P;
}
void calc(int o, ll v) {
	for(; o > 1; o >>= 1)
		ans = (ans + sum[o^1] * (o >> 1) % P * (v = v * o % P)) % P;
}
void slv(int l, int r, int o) {
	if(l == r) return w[l] = o, void();
	slv(lch), slv(rch);
	rep(i, l, mid) upd(bfn[p[i]], w[i] = w[i] * o % P);
	rep(i, mid + 1, r) calc(bfn[p[i]], w[i]), w[i] = w[i] * o % P;
	rep(i, l, mid) upd(bfn[p[i]], P - w[i]);
}
int main() {
	#ifdef local
		freopen("in.txt", "r", stdin);
	#endif
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	h = read(), l = 1 << (h - 1);
	rep(i, 1, l) p[i] = read(); 
	dfs(1, l, 1), slv(1, l, 1);
	return !(cout << ans);
}