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 <stdio.h>
#include <iostream>
#include <time.h>
#include <random>

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back
#define sqr(a) ((a) * (a))
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define forn(i, n) for(int i = 0; i < int(n); i++) 
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
	return out << "(" << a.x << ", " << a.y << ")";
}

template <class A> ostream& operator << (ostream& out, const vector<A> &v) {
	out << "[";
	forn(i, sz(v)) {
		if(i) out << ", ";
		out << v[i];
	}
	return out << "]";
}

mt19937 rnd(time(NULL));

const int INF = int(1e9);
const li INF64 = li(1e18);
const int MOD = int(1e9) + 7;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);

const int LOGN = 18;
const int N = 1 << LOGN;

int n;
int a[N], b[N];

bool read () {
	if (scanf("%d", &n) != 1)
		return false;
	forn(i, 1 << (n - 1)){
		scanf("%d", &a[i]);
		--a[i];
	}
	return true;
}

int add(int a, int b){
	a += b;
	if (a >= MOD)
		a -= MOD;
	if (a < 0)
		a += MOD;
	return a;
}

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

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

pt ch[N];
vector<int> t[N];
vector<pt> val[N];

void build(int v, int l, int r){
	ch[v] = mp(l, r);
	if (l == r - 1){
		t[v] = vector<int>(1, a[l]);
		val[v] = vector<pt>(1, mp(0, 0));
		int x = a[l] + (1 << (n - 1));
		int y = v;
		while (x > 0){
			y = mul(y, x);
			x /= 2;
		}
		val[v].pb(mp(y, y));
		return;
	}
	int m = (l + r) / 2;
	build(v * 2, l, m);
	build(v * 2 + 1, m, r);
	t[v].clear();
	val[v].clear();
	val[v].pb(mp(0, 0));
	int i = 0, j = 0;
	while (i < sz(t[v * 2]) || j < sz(t[v * 2 + 1])){
		if (j == sz(t[v * 2 + 1]) || (i < sz(t[v * 2]) && t[v * 2][i] < t[v * 2 + 1][j])){
			t[v].pb(t[v * 2][i]);
			val[v].pb(mp(val[v * 2][i + 1].x, 0));
			++i;
		}
		else{
			t[v].pb(t[v * 2 + 1][j]);
			val[v].pb(mp(val[v * 2 + 1][j + 1].x, 0));
			++j;
		}
	}
	forn(i, sz(t[v])){
		val[v][i + 1].x = mul(val[v][i + 1].x, v);
		val[v][i + 1].y = add(val[v][i].y, val[v][i + 1].x);
	}
}

int get(int v, int u){
	return add(val[v][lower_bound(all(t[v]), ch[u].y) - t[v].begin()].y, -val[v][lower_bound(all(t[v]), ch[u].x) - t[v].begin()].y);
}

int rev[N];

void solve() {
	build(1, 0, 1 << (n - 1));
	forn(i, N) rev[i] = binpow(i, MOD - 2);
	
	int ans = 0;
	forn(i, 1 << (n - 1)){
		int tmp = a[i] + (1 << (n - 1));
		int base = 1;
		while (tmp > 0){
			base = mul(base, rev[tmp]);
			tmp /= 2;
		}
		int ll = i + (1 << (n - 1));
		int prl = ll;
		int pl = ll / 2;
		while (pl > 0){
			prl = mul(prl, pl);
			int rr = a[i] + (1 << (n - 1));
			int prr = rr;
			int sr = base;
			int pr = rr / 2;
			while (pr > 0){
				prr = mul(prr, pr);
				sr = mul(sr, rr);
				ans = add(ans, mul(mul(get(ll ^ 1, rr ^ 1), sr), mul(prl, prr)));
				rr = pr;
				pr /= 2;
			}
			ll = pl;
			pl /= 2;
		}
	}
	
	printf("%d\n", mul(ans, (MOD + 1) / 2));
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	
	int tt = clock();
#endif
	
	cerr.precision(15);
	cout.precision(15);
	cerr << fixed;
	cout << fixed;

#ifdef _DEBUG
	while(read()) {	
#else
	if(read()) {
#endif
		solve();
		
#ifdef _DEBUG
	cerr << "TIME = " << clock() - tt << endl;
	tt = clock();
#endif

	}
}