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
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

const int MX = 1 << 18, md = 1000000007;

unordered_map<int, int> here[18];
bool old[18];

int a[MX];

int main() {
	int h = 18;
	ignore = scanf("%d", &h);
	
	int n = 1 << (h - 1);
	for (int i = 0; i < n; i++) ignore = scanf("%d", a + i);
//	srand(42);
//	iota(a, a + n, 1);
//	random_shuffle(a, a + n);
	
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int u = n + i, p = 1, d = 0; u != 1; d++, u /= 2) {
			p = p * 1LL * u % md;
			
			if (u % 2 == 0) {
				if (old[d]) {
					here[d].clear();
					old[d] = false;
				}
				
				for (int v = n + a[i] - 1, q = p; v != 1; v /= 2) {
					q = q * 1LL * v % md;
					
					int& val = here[d][v];
					val += q;
					if (val >= md) val -= md;
				}
			}
			else {
				old[d] = true;
				
				for (int v = n + a[i] - 1, q = p; v != 1; v /= 2) {
					q = q * 1LL * v % md;
					
					auto it = here[d].find(v ^ 1);
					if (it != here[d].end()) {
						int there = it->second;
						ans += q * 1LL * there % md * (v / 2) % md * (u / 2) % md;
						if (ans >= md) ans -= md;
					}
				}
			}
		}
	}
	
	printf("%d\n", ans);
	
	return 0;
}
