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<vector>
#include<set>
#include<map>
#include<queue>
#include<string>
#include<algorithm>
#include<iostream>
#include<bitset>
#include<functional>
#include<numeric>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<cmath>
#include<iomanip>
#include<random>
#include<ctime>
#include<complex>
using namespace std;
typedef long long LL;
typedef double D;
#define all(v) (v).begin(), (v).end()
mt19937 gene(233);
typedef complex<double> Complex;
#define fi first
#define se second
#define ins insert
#define pb push_back
inline char GET_CHAR(){
	const int maxn = 131072;
	static char buf[maxn],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,maxn,stdin),p1==p2)?EOF:*p1++;
}
inline int getInt() {
	int res(0);
	char c = getchar();
	while(c < '0') c = getchar();
	while(c >= '0') {
		res = res * 10 + (c - '0');
		c = getchar();
	}
	return res;
}

inline LL fastpo(LL x, LL n, LL mod) {
	LL res(1);
	while(n) {
		if(n & 1) {
			res = res * (LL)x % mod;
		}
		x = x * (LL) x % mod;
		n /= 2;
	}
	return res;
}
LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }

inline string itoa(int x, int width = 0) {
  string res;
  if(x == 0) res.push_back('0');
  while(x) {
    res.push_back('0' + x % 10);
    x /= 10;
  }
  while((int)res.size() < width) res.push_back('0');
  reverse(res.begin(), res.end());
  return res;
}
const int _B = 131072;
char buf[_B];
int _bl = 0;
inline void flush() {
	fwrite(buf, 1, _bl, stdout);
	_bl = 0;
}
__inline void _putchar(char c) {
	if(_bl == _B) flush();
	buf[_bl++] = c;
}
inline void print(LL x, char c) {
	static char tmp[20];
	int l = 0;
	if(!x) tmp[l++] = '0';
	else {
		while(x) {
			tmp[l++] = x % 10 + '0';
			x /= 10;
		}
	}
	for(int i = l - 1; i >= 0; i--) _putchar(tmp[i]);
	_putchar(c);
}
struct P {
	D x, y;
};
const int N = 1 << 18;
const int LOG = 20;
const int mod = 1e9 + 7;
const int inf = 1e9 + 7;
int n, m;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int a[N], inv[N], sum[N];
int s[N], is[N], v[N], u[N];
int uis[N], us[N], inu[N];
vector<pair<int, int> > evts[N];
void calc(int x, int * v) {
	for(int i = 0; i < n; i++) {
		v[i] = x;
		x /= 2;
	}
}
int main() {
	scanf("%d", &n);
	int L = (1 << (n - 1));
	for(int i = 0; i < L; i++) {
		int x;
		scanf("%d", &x);
		a[L + i] = x + L - 1;
		calc(L + i, v), calc(L + x - 1, u);
		for(int i = 0; i < n; i++) {
			s[i] = i == 0 ? v[i] : (LL)v[i] * s[i - 1] % mod;
			inv[i] = fastpo(v[i], mod - 2, mod);
		}
		for(int i = n - 1; i >= 0; i--) {
			is[i] = i == n - 1?  inv[i] : (LL)inv[i] * is[i + 1] % mod;
		}
		is[n] = 1;
		for(int i = 0; i < n; i++) {
			us[i] = i == 0 ? u[i] : (LL)u[i] * us[i - 1] % mod;
			inu[i] = fastpo(u[i], mod - 2, mod);
		}
		for(int i = n - 1; i >= 0; i--) {
			uis[i] = i == n - 1?  inu[i] : (LL)inu[i] * uis[i + 1] % mod;
		}
		uis[n] = 1;
		for(int j = 1; j < n; j++) {
			for(int k = 1; k < n; k++) {
				int y = u[k] * 4 + 1 - u[k - 1];
				int x = v[j] * 4 + 1 - v[j - 1];
				int lx = x << (j - 1);
				int rx = ((x + 1) << (j - 1)) - 1;
				int mul = s[j - 1] * (LL)is[j + 1] % mod % mod;
				mul = mul * (LL)us[k - 1] % mod * (LL)uis[k + 1] % mod;
				evts[lx - 1].pb(make_pair(y, - mul));
				evts[rx].pb(make_pair(y, mul));
			}
		}
	}
	LL ans = 0;
	map<pair<int, int>, int> mp;
	map<pair<int, int>, int> pm;
	
	for(int i = L; i < 2 * L; i++) {
		int t = 1;
		int x = a[i];
		while(x) {
			t = (LL)t * x % mod;
			x /= 2;
		}
		x = i;
		while(x) {
			t = (LL)t * x % mod;
			x /= 2;
		}
		x = a[i];
		//cout << t << ' ' << x << endl;
		while(x) {
			sum[x] = (sum[x] + t) % mod;
			//cout << "s" << x << ' ' << sum[x] << endl;
			x /= 2;
		}
		for(auto & tmp : evts[i]) {
			
			ans = (ans + sum[tmp.fi] * (LL)tmp.se) % mod;
		}
	}
	ans = (ans + mod) % mod;
	//cout << ans << endl;
	cout << ans * (LL)((mod + 1) / 2) % mod << endl;
}




