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>
#define ll long long
#define db long double
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define all(a) a.begin(), a.end()

using namespace std;

const int MOD = 1e9 + 7;
int N;

vector <int> p;
vector <int> sums;

int res = 0;

void add(int &x, int y) {
	x += y;
	if (x >= MOD) {
		x -= MOD;
	}
	if (x < 0) {
		x += MOD;
	}
}

void mult(int& x, int y) {
	x = x * (ll) y % MOD;
}

void dfs(int v, int w, int type) {
	mult(w, v);
	if (v >= N / 2) {
		int u = p[v - N / 2];
		int ww = 0;
		while (u) {
			if (type == 1) {
				mult(ww, u);
				int now = sums[u];
				add(now, -ww);
				//cout << v << " " << u << " " << w << " " << sums[u] << endl;
				add(res, now * (ll) w % MOD);
				add(ww, now);
				mult(w, u);
			} else {
				mult(w, u);
				add(sums[u], (type ? -1 : 1) * w);
			}
			u /= 2;
		}
	} else {
		dfs(2 * v, w, type);
		dfs(2 * v + 1, w, type);
	}
}

void iterate(int v) {
	if (v >= N / 2) {
		return;
	}
	iterate(2 * v);
	iterate(2 * v + 1);

	/*cout << "LCA: " << v << endl;
	cout << "WAS_RES : " << res << endl;*/

	dfs(2 * v, 1, 0);
	dfs(2 * v + 1, v, 1);
	dfs(2 * v, 1, 2);
}

int main(){
#ifdef LOCAL
	freopen("D_input.txt", "r", stdin);
	//freopen("D_output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;
	N = (1 << n);
	sums.resize(N, 0);
	for (int i = 0; i < N / 2; ++i) {
		int x;
		cin >> x;
		x += N / 2 - 1;
		p.pb(x);
	}
	/*for (int x : p) {
		cout << x << " ";
	}
	cout << endl;*/

	iterate(1);
	cout << res << "\n";
}
