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<cstdio>
const int mod = 1000000007;
int h;
int n;
int perm[300100];
long long int d[300100];
long long int ans;
void putleaf(int x, int prt, int val) {
	int y = x;
	long long int mult = val;
	while (y >= prt) {
		mult *= y;
		mult %= mod;
		y /= 2;
	}
	y = perm[x - n] + n;
	while (y >= 1) {
		d[y] += mult;
		d[y] %= mod;
		mult *= y;
		mult %= mod;
		y /= 2;
	}
}
void calcleaf(int x, int prt) {
	int y = x;
	long long int mult = 1;
	while (y > prt) {
		mult *= y;
		mult %= mod;
		y /= 2;
	}
	y = perm[x - n] + n;
	int prevy = -1;
	while (y >= 1) {
		mult *= y;
		mult %= mod;
		ans += mult * d[y];
		ans %= mod;
		if (prevy != -1) {
			ans += mod - (mult*d[prevy] % mod*prevy) % mod;
			ans %= mod;
		}
		prevy = y;
		y /= 2;
	}
}
int main() {
	scanf("%d", &h);
	n = 1 << (h - 1);
	for (int i = 0; i < n; i++) {
		scanf("%d", &perm[i]);
		perm[i]--;
	}
	ans = 0;
	for (int i = 0; i < h - 1; i++) {
		int base = 1 << i;
		for (int p = base; p < 2 * base; p++) {
			for (int leaf = ((p * 2) << (h - i - 2)); leaf < ((p * 2 + 1) << (h - i - 2)); leaf++) {
				putleaf(leaf, p, 1);
			}
			for (int leaf = ((p * 2 + 1) << (h - i - 2)); leaf < ((p * 2 + 2) << (h - i - 2)); leaf++) {
				calcleaf(leaf, p);
			}
			for (int leaf = ((p * 2) << (h - i - 2)); leaf < ((p * 2 + 1) << (h - i - 2)); leaf++) {
				putleaf(leaf, p, mod - 1);
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}
