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 <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <random>
#include <unordered_map>
#include <unordered_set>
#define all(a) a.begin(),a.end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define pb push_back
#define debug(x) cerr << #x << ':' << (x) << '\n'
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef complex<ld> com;
constexpr int inf = 1000000010;
constexpr ll INF = 1000000000000000010;
constexpr ld eps = 1e-12;
constexpr ld pi = 3.141592653589793238;
template<class T, class U> inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }

constexpr ll mod = 1000000007;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);

	int h;
	cin >> h;
	int sz = 1 << (h - 1);
	vector<int> p(sz);
	rep(i, sz) {
		cin >> p[i];
		p[i]--;
	}
	vector<vector<ll>> prod(sz, vector<ll>(h - 1));
	rep(i, sz) {
		ll x = i + sz; ll tmp = x;
		rep(j, h - 1) {
			prod[i][j] = tmp;
			x >>= 1;
			tmp *= x; tmp %= mod;
		}
	}
	vector<vector<P>> vec(2 * sz, vector<P>());
	vector<int> lst(2 * sz, -1);
	int bor = 1; int cap = 0;
	rep(i, 2 * sz) {
		if (i >= bor) {
			bor <<= 1;
			cap++;
		}
		int x = 1 << (h - cap);
		x *= (h - 1);
		if (i >= 2) vec[i].reserve(x);
	}
	rep(step, h - 1) {
		for (int i = sz - 1; i >= 0; i--) {
			int x = i + sz; int y = p[i] + sz;
			x >>= step;
			int idx = y;
			rep(j, h - 1) {
				if (lst[idx] == x) {
					vec[idx].back().first += prod[i][step] * prod[p[i]][j];
					vec[idx].back().first %= mod;
				}
				else {
					vec[idx].pb({ prod[i][step] * prod[p[i]][j] % mod,x });
					lst[idx] = x;
				}
				idx >>= 1;
			}
		}
	}
	rep(i, 2 * sz) {
		reverse(all(vec[i]));
		if (i & 1) {
			for (int j = 0; j < vec[i].size(); j++) {
				vec[i][j].second ^= 1;
				if (j > 0 && vec[i][j].second < vec[i][j - 1].second) swap(vec[i][j], vec[i][j - 1]);
			}
		}
	}
	ll ans = 0;
	for (int i = 0; i < 2 * sz; i += 2) {
		int x = 0, y = 0;
		while (x < vec[i].size() && y < vec[i + 1].size()) {
			if (vec[i][x].second < vec[i + 1][y].second) x++;
			else if (vec[i][x].second > vec[i + 1][y].second) y++;
			else {
				ans += vec[i][x].first * vec[i + 1][y].first % mod * (i >> 1) % mod * (vec[i][x].second >> 1);
				ans %= mod;
				x++; y++;
			}
		}
	}
	cout << ans << '\n';
}