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>

using namespace std;

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

int here[18][MX], last[18][MX], dead[18], alive[18];

int main() {
	int h;
	ignore = scanf("%d", &h);
	
	int n = 1 << (h - 1), ans = 0;
	for (int i = 0, a; i < n; i++) {
		ignore = scanf("%d", &a);
		
		for (int u = n + i, p = 1, d = 0; u != 1; d++, u /= 2) {
			p = p * 1LL * u % md;
			
			for (int v = n + a - 1, q = p; v != 1; v /= 2) {
				q = q * 1LL * v % md;
				
				if (u % 2 == 0) {
					alive[d] = dead[d];
					
					int& val = here[d][v];
					if (last[d][v] < alive[d]) {
						last[d][v] = alive[d];
						val = q;
					}
					else {
						val += q;
						if (val >= md) val -= md;
					}
				}
				else {
					dead[d]++;
					
					if (last[d][v ^ 1] == alive[d]) {
						int there = here[d][v ^ 1];
						ans += q * 1LL * there % md * (v / 2) % md * (u / 2) % md;
						if (ans >= md) ans -= md;
					}
				}
			}
		}
	}
	
	printf("%d\n", ans);
	
	return 0;
}
