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 <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#else
	#define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}


const ll MOD = (ll)1e9 + 7;
ll add(ll x, ll y) {
	x += y;
	if (x >= MOD) return x - MOD;
	return x;
}
ll sub(ll x, ll y) {
	x -= y;
	if (x < 0) return x + MOD;
	return x;
}
ll mult(ll x, ll y) {
	return (x * y) % MOD;
}
ll bin_pow(ll x, ll p) {
	if (p == 0) return 1;
	if (p & 1) return mult(x, bin_pow(x, p - 1));
	return bin_pow(mult(x, x), p / 2);
}
ll rev(ll x) {
	return bin_pow(x, MOD - 2);
}


const int N = (1 << 17);
const int M = N + 5;


int n;
int p[M];
int m;
vector<pii> a[2 * M];

int tryGet(int v, int p, int q) {
	q = max(0, min(q, (int)a[v].size() - 1));
	while(q >= 0 && a[v][q].first > p) q--;
	if (q < 0) return 0;
	while(q < (int)a[v].size() && a[v][q].first < p) q++;
	if (q == (int)a[v].size()) return 0;
	if (a[v][q].first == p)
		return a[v][q].second;
	else
		return 0;
}
void tryAdd(int v, int p, int x) {
	if (a[v].empty() || a[v].back().first != p)
		a[v].push_back(mp(p, x));
	else
		a[v].back().second = add(a[v].back().second, x);
}

int main()
{
	startTime = clock();
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);


	scanf("%d", &n);
	n = 1 << (n - 1);
	for (int i = 0; i < n; i++) {
		scanf("%d", &p[i]);
		p[i]--;
	}
/*
	n = 1 << 17;
	for (int i = 0; i < n; i++)
		p[i] = i;
	shuffle(p, p + n, rng);
*/
	int ans = 0;

	for (int i = 0; i < n; i++) {
		int x = n + i;
		int u = n + p[i];
		while(u > 1) {
			x = mult(x, u);
			a[n + i].push_back(mp(u, x));
			u /= 2;
		}
		reverse(all(a[n + i]));
	}
	for (int v = n - 1; v > 0; v--) {
		int p = 0, q = 0;
		while(p < (int)a[2 * v].size() || q < (int)a[2 * v + 1].size()) {
			if (p < (int)a[2 * v].size() &&
				(q == (int)a[2 * v + 1].size() ||
					a[2 * v][p] < a[2 * v + 1][q])) {
				int x = mult(a[2 * v][p].second, tryGet(2 * v + 1, a[2 * v][p].first ^ 1, q));
				x = mult(x, mult(v, a[2 * v][p].first / 2));
				ans = add(ans, x);
				tryAdd(v, a[2 * v][p].first, mult(a[2 * v][p].second, v));
				p++;
			} else {
				tryAdd(v, a[2 * v + 1][q].first, mult(a[2 * v + 1][q].second, v));
				q++;
			}
		}
	}
	printf("%d\n", ans);

	return 0;
}
