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
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using namespace std;

const ll MOD = 1e9 + 7;

ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}

const int N = 1 << 17;

int h, n;

int p[N];
ll go[N];

ll ans = 0;

ll gl[N * 2 + 5];
ll gr[N * 2 + 5];

int mx[N];
ll rgo[N * 2];

ll get(int x, int y) {
	ll ans = go[x] * go[y] % MOD;
	int lca = (x + n) >> mx[x ^ y];
	return ans * rgo[lca] % MOD;
}

void run(int v, int l, int r, ll cur) {
	ll nw = cur * pw(v, MOD - 2) % MOD;
	memset(gl, 0, sizeof(gl[0]) * (1 << h));
	memset(gr, 0, sizeof(gr[0]) * (1 << h));

	if ((r - l) <= 256) {
		for (int i = l; i < r; ++i) {
			for (int j = i + 1; j < r; ++j) {
				ans = (ans + get(i, j) * get(p[i], p[j])) % MOD;
			}
		}
		return;
	}

	int m = (l + r) >> 1;
	for (int i = l; i < m; ++i) {
		gl[n + p[i]] = (gl[n + p[i]] + go[i] * cur % MOD * (n + p[i])) % MOD;
	}
	for (int i = m; i < r; ++i) {
		gr[n + p[i]] = (gr[n + p[i]] + go[i] * nw % MOD * (n + p[i])) % MOD;
	}

	for (int i = n - 1; i >= 1; --i) {
		ll ad = (gl[i * 2] * gr[i * 2 + 1] + gl[i * 2 + 1] * gr[i * 2]) % MOD * i;
		ans = (ans + ad) % MOD;
		gl[i] = (gl[i * 2] + gl[i * 2 + 1]) * i % MOD;
		gr[i] = (gr[i * 2] + gr[i * 2 + 1]) * i % MOD;
	}

	run(v * 2, l, m, nw);
	run(v * 2 + 1, m, r, nw);
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cout.setf(ios::fixed), cout.precision(20);
	cin >> h;
	n = (1 << (h - 1));
	for (int i = 0; i < n; ++i) {
		cin >> p[i];
		--p[i];
	}
	for (int i = 0; i < n; ++i) {
		int cur = i;
		while (cur) {
			++mx[i];
			cur >>= 1;
		}
	}

	rgo[1] = 1;
	for (int i = 2; i < 2 * n; ++i) {
		rgo[i] = rgo[i / 2] * pw(i, MOD - 2) % MOD * pw(i / 2, MOD - 2) % MOD;
	}

	for (int i = 0; i < n; ++i) {
		ll cur = n + i;
		go[i] = 1;
		while (cur) {
			go[i] = (go[i] * cur) % MOD;
			cur >>= 1;
		}
	}

	run(1, 0, n, 1);
	cout << ans << "\n";

	return 0;
}


