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 <iostream>
#include <vector>
using namespace std;

const int LIMIT = 64;

// 入力
long long N;
long long Arr[1 << 19];
long long P[1 << 19];
long long Q[1 << 19];

// 計算
long long mod = 1000000007;
long long Answer = 0;
long long dep[1 << 19];
long long val[1 << 19];
long long inv[1 << 19];
long long val_inv[1 << 19];
long long val_inv2[1 << 19];
long long divs[1 << 19];

long long modpow(long long a, long long b, long long m) {
	long long p = 1, q = a;
	for (int i = 0; i < 32; i++) {
		if ((b / (1LL << i)) % 2LL == 1) { p *= q; p %= m; }
		q *= q; q %= m;
	}
	return p;
}

long long Div(long long a, long long b, long long m) {
	return (a * modpow(b, m - 2, m)) % m;
}

void init() {
	for (int i = 0; i < N; i++) {
		for (int j = (1 << i); j < (2 << i); j++) dep[j] = i;
	}
	for (int i = 0; i < (1 << N); i++) {
		long long cx = i;
		val[i] = 1;
		while (cx >= 1) {
			val[i] *= cx;
			val[i] %= mod;
			cx >>= 1;
		}
	}
	for (int i = 1; i < (1 << N); i++) inv[i] = Div(1, i, mod);
	for (int i = 1; i < (1 << N); i++) val_inv[i] = Div(1, val[i], mod);
	for (int i = 1; i < (1 << N); i++) val_inv2[i] = val_inv[i] * val_inv[i] % mod;
	for (int i = 1; i < (1 << N); i++) {
		divs[i] = inv[i];
		if (i >= 2) divs[i] *= val_inv2[i / 2];
		divs[i] %= mod;
	}
}

int getroot(int u, int v) {
	while (u != v) { u >>= 1; v >>= 1; }
	return u;
}

void dfs(int l, int r, int u, int h) {
	if (r - l == 1) return;
	int m = (l + r) / 2;

	if (r - l <= LIMIT) {
		long long ret = 0;
		for (int i = l; i < m; i++) {
			for (int j = m; j < r; j++) {
				int root = getroot((1 << (N - 1)) + Arr[i], (1 << (N - 1)) + Arr[j]);
				if (dep[root] >= h) continue;
				long long r1 = val[(1 << (N - 1)) + Arr[i]] * val[(1 << (N - 1)) + i] % mod;
				long long r2 = val[(1 << (N - 1)) + Arr[j]] * val[(1 << (N - 1)) + j] % mod;
				long long r3 = r1 * r2 % mod;
				ret += r3 * divs[root];
				ret %= mod;
			}
		}
		Answer += ret * divs[u];
		Answer %= mod;
	}
	else {
		// 木の計算
		if (h >= 1) {
			vector<long long> vec1(1 << (h + 1));
			vector<long long> vec2(1 << (h + 1));
			for (int i = l; i < r; i++) {
				int cx = (1 << (N - 1)) + Arr[i];
				while (cx >= 1) {
					if (cx < (1 << (h + 1))) {
						if (i < m) { vec1[cx] += val[(1 << (N - 1)) + Arr[i]] * val[(1 << (N - 1)) + i]; vec1[cx] %= mod; }
						else { vec2[cx] += val[(1 << (N - 1)) + Arr[i]] * val[(1 << (N - 1)) + i]; vec2[cx] %= mod; }
					}
					cx >>= 1;
				}
			}

			long long ret = 0;
			for (int i = 1; i < (1 << h); i++) {
				long long t1 = vec1[i * 2 + 0] * vec2[i * 2 + 1] % mod;
				long long t2 = vec1[i * 2 + 1] * vec2[i * 2 + 0] % mod;
				ret += (t1 + t2) * divs[i];
				ret %= mod;
			}
			Answer += ret * divs[u];
			Answer %= mod;
		}
	}

	// 再帰
	dfs(l, m, u * 2 + 0, h + 1);
	dfs(m, r, u * 2 + 1, h + 1);
}

int main() {
	// Step 1. 入力
	cin >> N;
	for (int i = 0; i < (1 << (N - 1)); i++) { cin >> P[i]; P[i]--; }
	for (int i = 0; i < (1 << (N - 1)); i++) { Q[P[i]] = i; }
	init();

	// Step 2. P における計算
	for (int i = 0; i < (1 << (N - 1)); i++) Arr[i] = P[i];
	dfs(0, (1 << (N - 1)), 1, 1);

	// Step 3. Q における計算
	for (int i = 0; i < (1 << (N - 1)); i++) Arr[i] = Q[i];
	dfs(0, (1 << (N - 1)), 1, 0);

	// Step 4. 出力
	cout << Answer << endl;
	return 0;
}