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 <bits/stdc++.h> 
using namespace std;

const int H = 20;
const long long mod = 1000000007ll;

template <class T>
void read(T &x) {
	int sgn = 1;
	char ch;
	x = 0;
	for (ch = getchar(); (ch < '0' || ch > '9') && ch != '-'; ch = getchar()) ;
	if (ch == '-') ch = getchar(), sgn = -1;
	for (; '0' <= ch && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
	x *= sgn;
}
template <class T>
void write(T x) {
	if (x < 0) putchar('-'), write(-x);
	else if (x < 10) putchar(x + '0');
	else write(x / 10), putchar(x % 10 + '0');
}

int h, perm[1 << H];
long long tmp[1 << H], ans = 0ll;

void add(int pos, long long val) {
	for (int i = pos; i; i >>= 1) {
		val = val * i % mod;
		tmp[i] = (tmp[i] + val) % mod; 
	}
}
void del(int pos) {
	for (int i = pos; i; i >>= 1) tmp[i] = 0ll;
}
void update(int pos, long long val) {
	for (int i = pos; i; i >>= 1) {
		val = val * i % mod;
		if (i > 1) ans = (ans + 1ll * tmp[i ^ 1] * val % mod * (i >> 1)) % mod;
	} 
}
void dfs1(int u, long long mul) {
	if ((u << 1 | 1) < (1 << h)) {
		dfs1(u << 1, mul * u % mod);
		dfs1(u << 1 | 1, mul * u % mod);
	} else add(perm[u], mul * u % mod);
}
void dfs2(int u, long long mul) {
	if ((u << 1 | 1) < (1 << h)) {
		dfs2(u << 1, mul * u % mod);
		dfs2(u << 1 | 1, mul * u % mod);
	} else update(perm[u], mul * u % mod); 
}
void dfs3(int u) {
	if ((u << 1 | 1) < (1 << h)) dfs3(u << 1), dfs3(u << 1 | 1);
	else del(perm[u]);
}

void dfs(int u) {
	if ((u << 1) < (1 << h)) dfs(u << 1);
	if ((u << 1 | 1) < (1 << h)) dfs(u << 1 | 1);
	if ((u << 1 | 1) << (1 << h)) {
		dfs1(u << 1, u);
		dfs2(u << 1 | 1, 1);
		dfs3(u << 1);
	} 
}
int main() {
	read(h);
	for (int i = (1 << (h - 1)); i < (1 << h); i++) read(perm[i]), perm[i] += (1 << (h - 1)) - 1;
	for (int i = 0; i < (1 << h); i++) tmp[i] = 0;
	dfs(1);
	write(ans), putchar('\n');
	return 0;
}