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 <utility>
#include <algorithm>
using namespace std;
#define F first
#define S second

typedef long long int ll;
constexpr int kMod = int(1E9 + 7), kN = int(3E5 + 10);

ll Pow(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1) ans = ans * a % kMod;
		a = a * a % kMod;
		b >>= 1;
	}
	return ans;
}
ll Rev(ll n) {return Pow(n, kMod - 2);}

int LCA(int l, int r) {
	while (l != r) {
		l >>= 1;
		r >>= 1;
	}
	return l;
}

struct seg_tree {
	ll val[kN << 2], flag[kN << 2];
	void init(int n, int l, int r) {
		val[n] = 0;
		flag[n] = 1;
		if (l < r) {
			int mid = (l + r) >> 1;
			init(n << 1, l, mid);
			init(n << 1 | 1, mid + 1, r);
		}
		return ;
	}
	void addtag(int n, ll x) {
		flag[n] = flag[n] * x % kMod;
		val[n] = val[n] * x % kMod;
		return ;
	}
	void push(int n) {
		if (flag[n] != 1) {
			addtag(n << 1, flag[n]);
			addtag(n << 1 | 1, flag[n]);
			flag[n] = 1;
		}
		return ;
	}
	void pull(int n) {
		val[n] = (val[n << 1] + val[n << 1 | 1]) % kMod;
		return ;
	}
	void set(int n, int l, int r, int pos, ll x) {
		if (l == r) val[n] = x;
		else {
			int mid = (l + r) >> 1;
			push(n);
			if (pos <= mid) set(n << 1, l, mid, pos, x);
			else set(n << 1 | 1, mid + 1, r, pos, x);
			pull(n);
		}
		return ;
	}
	void mul(int n, int l, int r, int L, int R, ll x) {
		if (L <= l && r <= R) addtag(n, x);
		else if (!(l > R || L > r)) {
			int mid = (l + r) >> 1;
			push(n);
			mul(n << 1, l, mid, L, R, x);
			mul(n << 1 | 1, mid + 1, r, L, R, x);
			pull(n);
		}
		return ;
	}
};

seg_tree sg;
int p[kN];
ll v[kN], x[kN], f[kN];

int main() {
	int h, l, tot, tmp, nxt;
	ll ans = 0; 
	scanf("%d", &h);
	l = (1 << (h - 1));
	for (int i = 1; i <= l; i++) scanf("%d", &p[i]);
	tot = (1 << h) - 1;
	v[0] = 1;
	v[1] = 1;
	for (int i = 1; i < l; i++) {
		v[i << 1] = (i << 1) * v[i] % kMod;
		v[i << 1 | 1] = (i << 1 | 1) * v[i] % kMod;
	}
	for (int i = l - 1; i >= 1; i--) v[i] = Rev(v[i >> 1] * v[i] % kMod);
	for (int i = 1; i <= l; i++) x[i] = v[l + i - 1] * v[l + p[i] - 1] % kMod;

	for (int j = 2; j <= l; j++) 
		f[j] = x[j] * v[LCA(l + 1 - 1, l + j - 1)] % kMod * v[LCA(l + p[1] - 1, l + p[j] - 1)] % kMod;
	sg.init(1, 1, l);
	for (int i = 2; i <= l; i++) sg.set(1, 1, l, p[i], f[i]);
	
	ans += x[1] * sg.val[1] % kMod;

	for (int i = 2; i <= l; i++) {
		sg.set(1, 1, l, p[i], 0);
		tmp = p[i - 1] - 1;
		for (int j = 0; j < h - 1; j++) { 
			nxt = tmp & -(1 << (j + 1));
			if (nxt != tmp) sg.mul(1, 1, l, nxt + 1, nxt + (1 << j), Rev(v[(l + tmp) >> (j + 1)]));
			else sg.mul(1, 1, l, tmp + (1 << j) + 1, tmp + (1 << (j + 1)), Rev(v[(l + tmp) >> (j + 1)]));
			tmp = nxt;
		}
		tmp = p[i] - 1;
		for (int j = 0; j < h - 1; j++) {
			nxt = tmp & -(1 << (j + 1));
			if (nxt != tmp) sg.mul(1, 1, l, nxt + 1, nxt + (1 << j), v[(l + tmp) >> (j + 1)]);
			else sg.mul(1, 1, l, tmp + (1 << j) + 1, tmp + (1 << (j + 1)), v[(l + tmp) >> (j + 1)]);
			tmp = nxt;
		}
		tmp = (i - 1) & -(i - 1);
		for (int j = 1; j < tmp; j++) {
			sg.mul(1, 1, l, p[i + j], p[i + j],
				Rev(v[LCA(l + i - 2, l + i - 1 + j)]) * v[LCA(l + i - 1, l + i - 1 + j)] % kMod); 
		}
		ans += x[i] * sg.val[1] % kMod;
	}
	ans %= kMod;
	//ans = ans * Rev(2) % kMod;
	printf("%lld\n", ans);
}
