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 mp make_pair
#define pb push_back

#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define rep(i, n) for (int i = 0; i < (int)(n); ++ i)

const int mxn = 1 << 18, mo = 1e9 + 7;

int qp(int x, int n) { int ans = 1; for (; n; n >>= 1, x = 1LL * x * x % mo) if (n & 1) ans = 1LL * ans * x % mo; return ans; }
int inv(int x) { return qp(x, mo - 2); }

int k, n, ans = 0;
int p[mxn], ma[mxn], mb[mxn], dfn[mxn];

void pre(int u, int l, int r, int ml) {
	static int tme = 0;
	dfn[u] = tme ++;
	mb[u] = ml;
	if (l + 1 == r) return ;
	int m = (l + r) >> 1;
	pre(u << 1, l, m, 1LL * ml * (u << 1) % mo);
	pre(u << 1 | 1, m, r, 1LL * ml * (u << 1 | 1) % mo);
}

int lca(int u, int v) { int x = 32 - __builtin_clz(u ^ v); return v >> x; }
int getfa(int u) { return u >> 1; }
int dep(int u) { return 32 - __builtin_clz(u); }
bool subt(int u, int v) {
	int du = dep(u), dv = dep(v);
	if (dv <= du) return 0;
	v >>= (dv - du);
	if (u != v) return 0;
	return 1;
}

bool comp(pair <int, pair <int, int> > a, pair <int, pair <int, int> > b) {
	return dfn[a.first] < dfn[b.first];
}

void virtree(vector <pair <int, pair <int, int> > > pnt) {
	sort(pnt.begin(), pnt.end(), comp);
	int psz = pnt.size();
	rep(i, psz - 1) pnt.pb(mp(lca(pnt[i].first, pnt[i + 1].first), mp(0, -1)));
	sort(pnt.begin(), pnt.end(), comp);
	int stk[20], top = 0;
	vector <int> fa(pnt.size());
	vector <vector <int> > g(pnt.size());
	rep(i, pnt.size()) {
		while (top && !subt(pnt[stk[top - 1]].first, pnt[i].first)) -- top;
		if (top) fa[i] = stk[top - 1], g[fa[i]].pb(i);
		else fa[i] = -1;
		stk[top ++] = i;
	}
	vector <int> dp[2];
	rep(c, 2) dp[c].resize(pnt.size());
	for (int i = (int) pnt.size() - 1; ~i; -- i) {
		int u = pnt[i].first;
		int s = pnt[i].second.first;
		int tp = pnt[i].second.second;
		if (tp >= 0) (dp[tp][i] += 1LL * s * mb[u] % mo) %= mo;
		if (~fa[i]) rep(c, 2) (dp[c][fa[i]] += dp[c][i]) %= mo;
		int ii = inv(1LL * mb[getfa(u)] * mb[u] % mo);
		if (g[i].size() == 2) {
			(ans += 1LL * dp[0][g[i][0]] * dp[1][g[i][1]] % mo * ii % mo) %= mo;
			(ans += 1LL * dp[1][g[i][0]] * dp[0][g[i][1]] % mo * ii % mo) %= mo;
		}
	}
}

void dfs(int u, int l, int r) {
	if (l + 1 == r) { ma[l] = u; return ; }
	int m = (l + r) >> 1;
	dfs(u << 1, l, m);
	dfs(u << 1 | 1, m, r);
	vector <pair <int, pair <int, int> > > pnt;
	for (int i = l; i < m; ++ i) pnt.pb(mp(p[i] + n, mp(1LL * ma[i] * u % mo, 0)));
	for (int i = m; i < r; ++ i) pnt.pb(mp(p[i] + n, mp(ma[i], 1)));
	virtree(pnt);
	for (int i = l; i < r; ++ i) ma[i] = 1LL * ma[i] * u % mo;
}

int main() {
	scanf("%d", &k); n = 1 << (k - 1);
	rep(i, n) scanf("%d", &p[i]), -- p[i];
	mb[0] = 1; pre(1, 0, n, 1); dfs(1, 0, n);
	printf("%d\n", ans);
	return 0;
}
