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 all(x) (x).begin(), (x).end()
#define itn int
#define make_unique(x) sort((x).begin(), (x).end()); (x).erase(unique((x).begin(), (x).end()), (x).end())

using namespace std;

inline int nxt() {
	int x;
	// scanf("%d", &x);
	cin >> x;
	return x;
}

const int mod = 1000000007;

int dif(int x, int y) {
	return x < y ? x - y + mod : x - y;
}

int prod(int x, int y) {
	return 1ll * x * y % mod;
}

void add(int& x, int y) {
	x += y;
	if (x >= mod) {
		x -= mod;
	}
}

using To = array<int, 2>;
struct Trie {
	int l;
	vector<To> a;
	vector<int> val;
	vector<int> par;

	Trie(int _l): l(_l), a(1, {{}}), val(1, 0), par(1, 0) {}

	int create(int v) {
		a.push_back({});
		val.push_back(0);
		par.push_back(v);
		return (int)a.size() - 1;
	}

	void add(int k, int v) {
		int u = 0;
		for (int i = (1 << (l - 1)); i > 0; i /= 2) {
			if (!a[u][!!(k & i)]) {
				int nw = create(u);
				a[u][!!(k & i)] = nw;
				// cerr << "created " << u << "->" << a[u][!!(k & i)] << " by " << !!(k & i) << "\n";
			}
			u = a[u][!!(k & i)];
		}
		while (u) {
			::add(val[u], v);
			u = par[u];
		}
		::add(val[u], v);
	}

	int proceed(int k) const {
		int u = 0;
		for (int i = (1 << (l - 1)); i > 0; i /= 2) {
			// cerr << u << " -> " << a[u][!!(k & i)] << " by " << !!(k & i) << "\n";
			u = a[u][!!(k & i)];
			assert(u);
		}
		return u;
	}

	void show() const {
		for (int i = 0; i < (int)a.size(); ++i) {
			for (int j : {0, 1}) {
				if (a[i][j]) {
					cerr << i << "->" << j << " ";
				}
			}
		}
		cerr << "\n";
	}
};

struct SegTree {
	int n;
	vector<vector<pair<int, int>>> a;
	vector<Trie> s;

	SegTree(const vector<pair<int, int>>& ar) {
		n = 1;
		while (n < (int)ar.size()) {
			n *= 2;
		}
		a.resize(n + n);
		for (int i = 0; i < (int)ar.size(); ++i) {
			a[n + i] = {ar[i]};
		}
		for (int i = n - 1; i > 0; --i) {
			a[i].resize(a[i + i].size() + a[i + i + 1].size());
			merge(all(a[i + i]), all(a[i + i + 1]), a[i].begin());
		}

		s.assign(n + n, __builtin_ctz(n));
		for (int i = 0; i < n + n; ++i) {
			for (const auto& [x, y] : a[i]) {
				s[i].add(x, y);
				// cerr << "added (" << x << ", " << y << ") to s[" << i << "]\n";
			}
			// s[i].resize(a[i].size() + 1);
			// for (int j = 0; j < (int)a[i].size(); ++j) {
			// 	s[i][j + 1] = (s[i][j] + a[i][j].second) % mod;
			// }
		}
	}

	// int getSingle(int v, int l, int r) {
	// 	auto idx_l = lower_bound(all(a[v]), pair{l, 0}) - a[v].begin();
	// 	auto idx_r = lower_bound(all(a[v]), pair{r, 0}) - a[v].begin();
	// 	return dif(s[v][idx_r], s[v][idx_l]);
	// }

	// int get(int l1, int r1, int l2, int r2) {
	// 	int l = 0, r = n;
	// 	int v = 1;
	// 	while (l < l1 || r > r1) {
	// 		int m = (l + r) / 2;
	// 		if (m >= r1) {
	// 			v *= 2;
	// 			r = m;
	// 		} else {
	// 			v = v * 2 + 1;
	// 			l = m;
	// 		}
	// 	}
	// 	return getSingle(v, l2, r2);
	// }
};

void solve() {
	int h = nxt() - 1;
	int n = 1 << h;
	vector<int> inv(n + n + 1, 1);
	for (int i = 2; i < (int)inv.size(); ++i) {
		inv[i] = dif(0, prod(mod / i, inv[mod % i]));
	}

	vector<int> score(n + n), invscore(n + n), huinvscore(n + n);
	for (int i = 1; i < n + n; ++i) {
		score[i] = i;
		invscore[i] = inv[i];
		if (i > 1) {
			score[i] = prod(score[i], score[i / 2]);
			invscore[i] = prod(invscore[i], invscore[i / 2]);
		}
		huinvscore[i] = invscore[i];
		if (i > 1) {
			huinvscore[i] = prod(huinvscore[i], invscore[i / 2]);
		}
	}

	vector<int> bitchscore(n + n);
	for (int i = 1; i < n + n; ++i) {
		bitchscore[i] = huinvscore[i];
		if (i > 1) {
			bitchscore[i] = dif(bitchscore[i], huinvscore[i / 2]);
		}
	}

	vector<pair<int, int>> lrs(n + n);
	for (int i = 0; i < n; ++i) {
		lrs[n + i] = {i, i + 1};
	}
	for (int i = n - 1; i > 0; --i) {
		lrs[i] = {lrs[i + i].first, lrs[i + i + 1].second};
	}

	vector<int> p(n);
	for (int i = 0; i < n; ++i) {
		p[i] = nxt() - 1;
	}

	vector<pair<int, int>> nether(n);
	for (int i = 0; i < n; ++i) {
		nether[p[i]] = {i, prod(score[n + i], score[n + p[i]])};
	}
	SegTree tree(nether);

	int ans = 0;
	for (int e = 0; e < n; ++e) {
		for (int y = p[e] + n; y; y /= 2) {
			// cerr << e << " " << y << "\n";
			int v = y;
			const auto& trie = tree.s[v];
			// cerr << "proceeding to " << e << " in s[" << v << "]\n";
			int ptr = trie.proceed(e);
			for (int x = e + n; x; x /= 2) {
				// if (prod(prod(bitchscore[x], bitchscore[y]), prod(nether[p[e]].second, dif(tree.get(lrs[y].first, lrs[y].second, lrs[x].first, lrs[x].second), nether[p[e]].second)))) {
				// 	cerr << x << " " << y << " (" << e + n << " -- " << p[e] + n << "): " << prod(prod(bitchscore[x], bitchscore[y]), prod(nether[p[e]].second, dif(tree.get(lrs[y].first, lrs[y].second, lrs[x].first, lrs[x].second), nether[p[e]].second))) << "\n";
				// }

				// add(ans, prod(prod(bitchscore[x], bitchscore[y]), prod(nether[p[e]].second, dif(tree.get(lrs[y].first, lrs[y].second, lrs[x].first, lrs[x].second), nether[p[e]].second))));
				add(ans, prod(prod(bitchscore[x], bitchscore[y]), prod(nether[p[e]].second, dif(trie.val[ptr], nether[p[e]].second))));
				ptr = trie.par[ptr];
			}
		}
	}

	if (ans % 2) {
		ans += mod;
	}
	ans /= 2;
	cout << ans << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);

	int t = 1; // nxt();
	while (t--) {
		solve();
	}

	return 0;
}
