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 <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <complex>


using namespace std;
template<typename T1, typename T2> inline void chkmin(T1 &a, T2 b) {if (a > b) a = b;}
template<typename T1, typename T2> inline void chkmax(T1 &a, T2 b) {if (a < b) a = b;}
#define files(FILENAME) read(FILENAME); write(FILENAME)
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define left left228
#define right right228
#define y1 y1228
#define mp make_pair
#define pb push_back
#define y2 y2228
#define rank rank228
using ll = long long;
using ld = long double; 
const string FILENAME = "input";
const int Mod = 1000000007;
const int MAXN = 1 << 18;


int sum(int a, int b) {
	return (a + b >= Mod ? a + b - Mod: a + b);
}


void adds(int &a, const int b) {
	a += b;
	if (a >= Mod) {
		a -= Mod;
	}
}

int mul(int a, int b) {
	return ((ll)a * b % Mod);
}


int powm(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) {
			res = mul(res, a);
		} 
		b >>= 1;
		a = mul(a, a);
	} 
	return res;
}


int h;
int L;
int p[MAXN];
int mult[MAXN];
int rmult[MAXN];
vector<pair<int, int> > g[MAXN];
vector<int> pref[MAXN];
int l[MAXN], r[MAXN];
vector<pair<pair<int, int>, int> > z[MAXN];
vector<int> g1[MAXN];
int val[MAXN];



void inc(int i, int vals) {
	for (; i <= L; i |= (i + 1)) {
		adds(val[i], vals);
	}
}


int get(int i) {
	int res = 0;
	for (; i >= 0; i = (i & (i + 1)) - 1) {
		adds(res, val[i]);
	}
	return res;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//read(FILENAME);
	cin >> h;
	//h = 18;
	L = (1 << (h - 1));
	for (int i = 0; i < L; i++) {
		cin >> p[i];
		//p[i] = i + 1;
	}
	// mt19937 as;
	//shuffle(p, p + L, as);
	for (int i = 0; i < L; i++) {
		g[i + L].pb(mp(p[i], L + i));
		l[i + L] = i + 1;
		r[i + L] = i + 1;
	}
	rmult[0] = 1;
	mult[0] = 1;
	for (int i = 1; i < 2 * L; i++) {
		mult[i] = mul(i, mult[i >> 1]);
		rmult[i] = powm(mult[i], Mod - 2);
	}
	for (int i = L - 1; i >= 1; i--) {
		l[i] = l[i * 2];
		r[i] = r[i * 2 + 1];
	}
	for (int i = 0; i < L; i++) {
		int id = L + i;
		while (id >> 1 > 0) {
			int prev = id;
			id >>= 1;
			z[id].pb(mp(mp(prev, L + i), p[i] + L - 1));
		}
	}
	for (int i = 0; i < L; i++) {
		g1[i + L].pb(g[i + L][0].first);
		pref[i + L].pb(mul(mult[g[i + L][0].first + L - 1], mult[g[i + L][0].second]));
	}
	ll ans = 0;
	for (int i = L - 1; i >= 1; i--) {
		g[i].resize(sz(g[i * 2]) + sz(g[i * 2 + 1]));
		merge(all(g[i * 2]), all(g[i * 2 + 1]), g[i].begin());
		pref[i].resize(sz(g[i]));
		g1[i].resize(sz(g[i]));
		for (int j = 0; j < sz(g[i]); j++) {
			g1[i][j] = g[i][j].first;
			pref[i][j] = mul(mult[g[i][j].first + L - 1], mult[g[i][j].second]);
		}
		for (int j = 0; j < sz(g[i * 2]); j++) {
			inc(g[i * 2][j].first, pref[i * 2][j]);
		}
		for (auto x: z[i]) {
			int c = (i * 2) ^ (i * 2 + 1) ^ x.first.first;
			if (c == i * 2) {
			int posi = x.first.second;
			int mod = mul(mult[posi], rmult[i >> 1]);
			mod = mul(mod, rmult[i]);
			mod = mul(mod, mult[x.second]);
			int cur = x.second;
			while (cur >> 1 > 0) {
				int pcur = cur;
				cur >>= 1;
				int tcur = (cur * 2) ^ (cur * 2 + 1) ^ pcur;
				int fl = l[tcur];
				int fr = r[tcur];
				int res = sum(get(fr), Mod - get(fl - 1));
				res = mul(res, rmult[cur >> 1]);
				res = mul(res, rmult[cur]);
				res = mul(res, mod);
				ans = sum(ans, res);
			}
			}
		}
		for (int j = 0; j < sz(g[i * 2]); j++) {
			inc(g[i * 2][j].first, Mod - pref[i * 2][j]);
		}
		for (int j = 0; j < sz(g[i * 2 + 1]); j++) {
			inc(g[i * 2 + 1][j].first, pref[i * 2 + 1][j]);
		}
		for (auto x: z[i]) {
			int c = (i * 2) ^ (i * 2 + 1) ^ x.first.first;
			if (c == i * 2 + 1) {
			int posi = x.first.second;
			int mod = mul(mult[posi], rmult[i >> 1]);
			mod = mul(mod, rmult[i]);
			mod = mul(mod, mult[x.second]);
			int cur = x.second;
			while (cur >> 1 > 0) {
				int pcur = cur;
				cur >>= 1;
				int tcur = (cur * 2) ^ (cur * 2 + 1) ^ pcur;
				int fl = l[tcur];
				int fr = r[tcur];
				int res = sum(get(fr), Mod - get(fl - 1));
				res = mul(res, rmult[cur >> 1]);
				res = mul(res, rmult[cur]);
				res = mul(res, mod);
				ans = sum(ans, res);
			}
			}
		}
		for (int j = 0; j < sz(g[i * 2 + 1]); j++) {
			inc(g[i * 2 + 1][j].first, Mod - pref[i * 2 + 1][j]);
		}
	}
	ans = mul(ans, powm(2, Mod - 2));
	cout << ans << '\n';
}
