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>

template <class T>
inline void read(T &x) {
	static char ch; 
	static bool opt; 
	while (!isdigit(ch = getchar()) && ch != '-'); 
	x = (opt = ch == '-') ? 0 : ch - '0'; 
	while (isdigit(ch = getchar()))
		x = x * 10 + ch - '0'; 
	if (opt)
		x = ~x + 1; 
}

template <class T>
inline void putint(T x) {
	static char buf[45], *tail = buf; 
	if (!x)
		putchar('0'); 
	else {
		if (x < 0)
			putchar('-'), x = ~x + 1; 
		for (; x; x /= 10) *++tail = x % 10 + '0'; 
		for (; tail != buf; --tail) putchar(*tail); 
	}
}

template <class T>
inline bool tense(T &x, const T &y) {
	return y < x ? x = y, true : false; 
}

template <class T>
inline bool relax(T &x, const T &y) {
	return x < y ? x = y, true : false; 
}

template <class T>
inline T getAbs(const T &x) {
	return x < 0 ? -x : x; 
}

typedef long long s64; 
typedef long double ld; 
typedef std::vector<int> vi; 
typedef std::pair<int, int> pii; 
#define mp(x, y) std::make_pair(x, y)

const int mod = 1e9 + 7; 
inline void add(int &x, const int &y) {
	if (x += y, x >= mod) x -= mod; 
}
inline void dec(int &x, const int &y) {
	if (x -= y, x < 0) x += mod; 
}
inline int qpow(int x, int y) {
	int res = 1; 
	for (; y; y >>= 1, x = 1LL * x * x % mod)
		if (y & 1) res = 1LL * res * x % mod; 
	return res; 
}

const int MaxN = 1 << 18 | 5; 

int H, n, m; 
int p[MaxN], prod[MaxN], pinv[MaxN]; 

int s[MaxN], sum; 

void modify(int x, int opt) {
	if (x >= m) {
		int val = 1LL * prod[x] * prod[p[x]] % mod; 
		for (int y = p[x]; y; y >>= 1)
			(opt == 1 ? add : dec)(s[y], val); 
		return; 
	}
	modify(x << 1 | 0, opt); 
	modify(x << 1 | 1, opt); 
}

void query(int x) {
	if (x >= m) {
		int val = 1LL * prod[x] * prod[p[x]] % mod; 

		for (int y = p[x]; y > 1; y >>= 1) {
			add(sum, 1LL * val * pinv[y >> 1] % mod * s[y ^ 1] % mod); 
		}
		return; 
	}
	query(x << 1 | 0); 
	query(x << 1 | 1); 
}

int main() {
#ifdef orzczk
	freopen("a.in", "r", stdin); 
#endif

	read(H); 
	n = 1 << H, m = (n + 1) >> 1; 

	pinv[0] = 1, prod[1] = pinv[1] = 1; 
	for (int i = 2; i < n; ++i) {
		prod[i] = 1LL * prod[i >> 1] * i % mod; 
		pinv[i] = qpow(1LL * prod[i] * prod[i >> 1] % mod, mod - 2); 
	}

	for (int i = m; i < n; ++i) {
		read(p[i]); 
		p[i] += m - 1; 
	}

	int ans = 0; 
	for (int x = 1; x < m; ++x) {
		modify(x << 1, +1); 

		sum = 0; 
		query(x << 1 | 1); 
		ans = (ans + 1LL * sum * pinv[x]) % mod; 
		
		modify(x << 1, -1); 
	}

	std::cout << ans << '\n'; 

	return 0; 
}