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>

typedef long long LL;

const int MAXN = 1 << 18 | 1, MOD = 1e9 + 7;
inline int add(int x, int y) { return x + y >= MOD ? x + y - MOD : x + y; }
inline int sub(int x, int y) { return x < y ? x - y + MOD : x - y; }
inline int mul(int x, int y) { return 1LL * x * y - 1LL * x * y / MOD * MOD; }
inline int Qpow(int a, int b) { int ans = 1; for (; b; a = mul(a, a), b >>= 1) if (b & 1) ans = mul(ans, a); return ans; }

int n, l, h, ans;
int p[MAXN], val[MAXN];

template <int N, int S>
struct Trie {
	int QAQ[N];
	inline void insert(int x, int val) { for (; x > 1; x >>= 1) val = mul(val, x), QAQ[x] = add(QAQ[x], val); }
	inline int query(int x) {
		int ans = 0, pro = 1;
		for (; x > 1; x >>= 1) pro = mul(pro, x), ans = add(ans, mul(mul(QAQ[x ^ 1], pro), x >> 1));
		return ans;
	}
};
Trie <MAXN, 2> T;

void gao(int x, int L, int R) {
	if (L < R) {
		int mid = (L + R) >> 1;
		gao(x << 1, L, mid), gao(x << 1 | 1, mid + 1, R);
		for (int i = L; i <= mid; ++i) T.insert(p[i] + l - 1, val[i]);
		for (int i = mid + 1; i <= R; ++i) ans = add(ans, mul(mul(x, val[i]), T.query(p[i] + l - 1)));
		for (int i = L; i <= mid; ++i) T.insert(p[i] + l - 1, MOD - val[i]);
	}
	for (int i = L; i <= R; ++i) val[i] = mul(val[i], x);
}

int main() {
	scanf("%d", &h), n = (1 << h) - 1, l = 1 << (h - 1);
	for (int i = 1; i <= l; ++i) scanf("%d", p + i);
	for (int i = 1; i <= l; ++i) val[i] = 1;
	gao(1, 1, l);
	printf("%d\n", ans);
	return 0;
}