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 <iomanip>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;
#define int long long
#define endl '\n'
typedef long long ll;

const int N = (1<<18) + 10, mod = 1e9 + 7;
int h;
int perm[N], saveVal[N];
vector<int> nodesInSaveVal;

void dfs1(int node, int pathProd) {
	pathProd = (pathProd * node) % mod;
	if(node >= (1<<(h-1))) {//node is leaf
		int nodeOther = perm[node];
		while(true) {
			pathProd *= nodeOther;
			pathProd %= mod;
			nodesInSaveVal.push_back(nodeOther);
			saveVal[nodeOther] += pathProd;
			saveVal[nodeOther] %= mod;
			if(nodeOther == 1) break;
			nodeOther /= 2;
		}
	} else {
		dfs1(2*node, pathProd);
		dfs1(2*node+1, pathProd);
	}
}

int currSum;

void dfs2(int node, int pathProd) {
	pathProd = (pathProd * node) % mod;
	if(node >= (1<<(h-1))) {//node is leaf
		int nodeOther = perm[node];
		int prevNode = nodeOther;
		while(true) {
			pathProd *= nodeOther;
			pathProd %= mod;

			if(prevNode > nodeOther) {
				currSum += (pathProd * saveVal[prevNode^1]) % mod;
			}
			currSum %= mod;
			if(nodeOther == 1) break;
			prevNode = nodeOther;
			nodeOther /= 2;
		}
	} else {
		dfs2(2*node, pathProd);
		dfs2(2*node+1, pathProd);
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> h;
	for(int i = (1<<(h-1)); i < (1<<h); ++i) {
		cin >> perm[i];
		perm[i] += (1<<(h-1)) - 1;
	}
	int res = 0;
	for(int lca = 1; lca < (1<<(h-1)); ++lca) {
		int L = 2*lca;
		int R = 2*lca + 1;
		nodesInSaveVal.clear();
		dfs1(L,1);
		currSum = 0;
		dfs2(R,1);
		res += (lca * currSum) % mod;
		res %= mod;
		for(int node : nodesInSaveVal) {
			saveVal[node] = 0;
		}
	}
	cout << res;
}
