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;

#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lch (o << 1)
#define rch (o << 1 | 1)

typedef double db;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int, int> pint;
typedef tuple<int, int, int> tint;

const int N = (1 << 18) + 5;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;

vector<int> son[N];
int p[N];
ll s[N], prod[N], iprod[N];
int h, n;
ll ans;

ll QPow(ll bas, int t) {
	ll ret = 1;
	while (t) {
		if (t & 1) ret = ret * bas % MOD;
		bas = bas * bas % MOD;
		t >>= 1;
	}
	return ret;
}

void DFS(int o) {
	if (lch > n) {
		son[o].push_back(o);
		return;
	}
	DFS(lch);
	DFS(rch);

	// tag lch
	for (auto u: son[lch]) {
		int v = p[u];
		ll w = prod[u] * prod[v] % MOD;
		while (v) {
			s[v] = (s[v] + w) % MOD;
			v /= 2;
		}
	}

	// cal rch
	ll sum = 0;
	for (auto u: son[rch]) {
		int v = p[u];
		ll w = prod[u] * prod[v] % MOD;
		ll pre = 0;
		while (v) {
			sum = (sum + w * (s[v] - pre) % MOD * iprod[v] % MOD * iprod[v / 2]) % MOD;
			pre = s[v];
			v /= 2;
		}
	}
	ans = (ans + sum * iprod[o] % MOD * iprod[o / 2]) % MOD;

	// clear tag
	for (auto u: son[lch]) {
		int v = p[u];
		while (v) {
			s[v] = 0;
			v /= 2;
		}
	}

	son[o].insert(son[o].end(), all(son[lch]));
	son[o].insert(son[o].end(), all(son[rch]));
}

int main() {
	ios::sync_with_stdio(0);

	prod[0] = iprod[0] = 1;
	for (int i = 1; i < N; i++) {
		prod[i] = prod[i / 2] * i % MOD;
		iprod[i] = QPow(prod[i], MOD - 2);
	}

	cin >> h;
	n = (1 << h) - 1;
	for (int i = 1; i <= n / 2 + 1; i++) {
		int pos;
		cin >> pos;
		p[i + n / 2] = pos + n / 2;
	}
	DFS(1);
	ans = (ans % MOD + MOD) % MOD;
	cout << ans << endl;

	return 0;
}
