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 ll long long
#define db long double
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define all(a) a.begin(), a.end()

using namespace std;

const int mod = 1000000007;
const int N = 300007;

int bp(int x, int y) {
	if (y==0) return 1;
	if (y==1) return x%mod;

	if (y%2) return ((ll) x * bp(x, y-1)) % mod;
	int t = bp(x, y/2);

	return ((ll) t * t) % mod;

}

int rv[N];

int n;

int ans = 0;
void solve3(int l, int r, int Q, vector<tuple<int, int, int> > &kek, int tut) {

	Q = ((ll) Q * rv[tut]) % mod;
	int mid = (l+r)/2;

	int a = 0, b = 0, c = 0, d = 0, e=0, f=0;
	for (auto x : kek) {
		if (get<0>(x) < mid) {
			if (get<2>(x) == 1) {
				e++;
				a += get<1>(x);
				if (a >= mod) a -= mod;
			}
			else {
				f++;
				b += get<1>(x);
				if (b >= mod) b -= mod;
			}
		}

		else {
			if (get<2>(x) == 1) {
				e++;
				c += get<1>(x);
				if (c >= mod) c -= mod;
			}
			else {
				f++;
				d += get<1>(x);
				if (d >= mod) d -= mod;
			}
		}
	}

	if (e==0 || f==0) return;
	int T = ((ll) Q * a) % mod;
	T =((ll) T * d) % mod;

	ans += T;
	if (ans >= mod) ans -= mod;

	T = ((ll) Q * b) % mod;
	T =((ll) T * c) % mod;

	ans += T;
	if (ans >= mod) ans -= mod;

	vector<tuple<int, int, int> > fv, sv;
	for (auto x : kek) {
		if (get<0>(x) < mid) fv.pb(x);
		else sv.pb(x);
	}

	Q = ((ll) Q * rv[tut]) % mod;

	solve3(l, mid, Q, fv, 2*tut);
	solve3(mid, r, Q, sv, 2*tut+1);

	



}

void solve2(vector<int> &a, vector<int> &b, int M, int step, vector<int> &perm) {

	vector<int> w1, w2;

	int u = 0;

	for (auto x : a) {

		x += n;

		int now = 1;
		int y = x;

		while (true) {
			now = ((ll) now * y) % mod;
			if (y == M) break;
			y = y/2;
		}

		y = perm[step + u] + n;

		while (true) {
			now = ((ll) now * y) % mod;
			if (y == 1) break;
			y = y/2;
		}		

		u++;
		w1.pb(now);

	}

	for (auto x : b) {

		x += n;

		int now = 1;
		int y = x;

		while (true) {
			now = ((ll) now * y) % mod;
			if (y == M) break;
			y = y/2;
		}

		y = perm[step + u] + n;

		while (true) {
			now = ((ll) now * y) % mod;
			if (y == 1) break;
			y = y/2;
		}		

		u++;
		w2.pb(now);

	}

	M = rv[M];

	vector<tuple<int, int, int> > kek;
	for (int i = 0; i < a.size(); ++i) {
		kek.pb(make_tuple(perm[step + i], w1[i], 1));
		kek.pb(make_tuple(perm[step + i + a.size()], w2[i], 2));
	}

	sort(all(kek));

	solve3(0, n, M, kek, 1);


}

void solve(int l, int r, vector<int> &v, int tut) {

	if (r - l == 1) return;
	vector<int> a, b;
	int mid = (l+r)/2;

	for (int i = l; i < mid; ++i) a.pb(i);
	for (int i = mid; i < r; ++i) b.pb(i);

	solve2(a, b, tut, l, v);

	solve(l, mid, v, 2*tut);
	solve(mid, r, v, 2*tut+1);

}

int main(){
#ifdef LOCAL
	freopen("D_input.txt", "r", stdin);
	//freopen("D_output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 1; i < N; ++i) {
		rv[i] = bp(i, mod-2);
	}

	cin >> n;

	n = (1<<(n-1));

	vector<int> v(n);
	for (int i = 0; i < n; ++i) {
		cin >> v[i];
		v[i]--;
	}

	solve(0, n, v, 1);

	cout << ans;

}
