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
/*

Code for problem D by cookiedoth
Generated 09 Aug 2020 at 04.55 PM


──────▄▌▐▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▌
───▄▄██▌█░ВЕЗЁМ▄▀▀▀▄░ГУСЕЙ░░░░░░░
───████▌█▄███▀░◐░▄▀▀▀▄░░РАБОТЯГИ░
──██░░█▌█░░▄███▀░◐░░▄▀▀▀▄░░░░░░░
─██░░░█▌█░░░░▐░▄▀▀▀▌░░░░◐░▀███▄░
▄██████▌█▄███▀░◐░░░▌░░░░░▐░░░░░░
███████▌█░░░░▌░░░░░▌░░░░░▐░░░░░░
███████▌█▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▌
▀(@)▀▀▀▀▀▀▀(@)(@)▀▀▀▀▀▀▀▀▀▀▀▀▀(@)▀(@)

¯\_(ツ)_/¯
^_^
~_^

*/

#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <complex>
#include <cassert>
#include <random>
#include <cstring>
#include <numeric>
#define int long long
#define ll long long
#define ld long double
#define null NULL
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define debug(a) cerr << #a << " = " << a << endl
#define forn(i, n) for (int i = 0; i < n; ++i)
#define sz(a) (int)a.size()

using namespace std;

template<class T> int chkmax(T &a, T b) {
	if (b > a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class T> int chkmin(T &a, T b) {
	if (b < a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class iterator> void output(iterator begin, iterator end, ostream& out = cerr) {
	while (begin != end) {
		out << (*begin) << " ";
		begin++;
	}
	out << endl;
}

template<class T> void output(T x, ostream& out = cerr) {
	output(x.begin(), x.end(), out);
}

void fast_io() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

const int MOD = 1e9 + 7;

int mul(int a, int b) {
	return (1LL * a * b) % MOD;
}

int power(int a, int deg) {
	int res = 1;
	for (; deg; a = mul(a, a), deg >>= 1) {
		if (deg & 1) {
			res = mul(res, a);
		}
	}
	return res;
}

int inverse(int a) {
	return power(a, MOD - 2);
}

struct st {
	int n, used_clr;
	vector<int> t, used;

	void init(int _n) {
		n = _n;
		used_clr = 0;
		t.resize(2 * n);
		used.resize(2 * n);
	}

	void add(int pos, int val, int _used_clr) {
		// cerr << (this) << ".add " << pos  << " " << val << " " << _used_clr << endl;
		used_clr = _used_clr;
		pos += n;
		while (pos) {
			if (used[pos] != used_clr) {
				used[pos] = used_clr;
				t[pos] = 0;
			}
			t[pos] = (t[pos] + val) % MOD;
			pos /= 2;
		}
	}

	int get(int v) {
		return (used[v] == used_clr ? t[v] : 0);
	}
};

const int mx = 3e5 + 228;
int H, n, p[mx], pref[mx], lca_pen[mx];

void read() {
	cin >> H;
	n = (1 << (H - 1));
	for (int i = 0; i < n; ++i) {
		cin >> p[i];
		p[i]--;
	}
	for (int i = 0; i < n; ++i) {
		int v = n + i;
		pref[i] = 1;
		while (v > 1) {
			pref[i] = mul(pref[i], v);
			v /= 2;
		}
	}
	for (int i = 1; i < n; ++i) {
		lca_pen[i] = i;
		int v = i;
		while (v > 1) {
			int _v = inverse(v);
			lca_pen[i] = mul(lca_pen[i], mul(_v, _v));
			v /= 2;
		}
	}
}

int ans, used_clr;
st T[2];

void init() {
	for (int i = 0; i < 2; ++i) {
		T[i].init(n);
	}
}

int v0;

void process(int v, int l, int r) {
	if (l == r) {
		return;
	}
	if (T[0].get(v) == 0 && T[1].get(v) == 0) {
		return;
	}
	int res1 = mul(T[0].get(v * 2), T[1].get(v * 2 + 1));
	int res2 = mul(T[0].get(v * 2 + 1), T[1].get(v * 2));
	int res = (res1 + res2) % MOD;
	res = mul(res, mul(lca_pen[v0], lca_pen[v]));
	// cerr << "res = " << res << endl;
	ans = (ans + res) % MOD;
	int mid = (l + r) >> 1;
	process(v * 2, l, mid);
	process(v * 2 + 1, mid + 1, r);
}

void divide(int v, int l, int r) {
	if (l == r) {
		return;
	}
	v0 = v;
	used_clr++;
	int mid = (l + r) >> 1;
	for (int i = l; i <= r; ++i) {
		T[i <= mid].add(p[i], mul(pref[p[i]], pref[i]), used_clr);
	}
	// cerr << "process " << l << " " << r << endl;
	process(1, 0, n - 1);
	divide(2 * v, l, mid);
	divide(2 * v + 1, mid + 1, r);
}

signed main() {
	fast_io();
	read();
	init();
	divide(1, 0, n - 1);
	cout << ans << '\n';
}
