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>
#define maxn 1000086

using namespace std;

const int p = 1e9 + 7;

int h, l;
int P[maxn];
int ans;
int a[maxn][2];
int sk[maxn], top;

void dfs1(int i, int sum){
	sum = 1ll * sum * i % p;
	if(i >= l){
		sk[++top] = i = l + P[i - l + 1] - 1;
		sum = 1ll * sum * i % p;
		int x = i & 1;
		i >>= 1;
		while(i){
			sum = 1ll * sum * i % p;
			a[i][x] = (a[i][x] + sum) % p;
			x = i & 1, i >>= 1;
		}
		return;
	}else{
		dfs1(i << 1, sum), dfs1(i << 1 | 1, sum);
	}
}

void dfs2(int i, int sum){
	sum = 1ll * sum * i % p;
	if(i >= l){
		i = l + P[i - l + 1] - 1;
		sum = 1ll * sum * i % p;
		int x = i & 1;
		i >>= 1;
		while(i){
			ans = (ans + 1ll * a[i][x ^ 1] * sum) % p;
			//printf("%d %d--\n", i, 1ll * a[i] * sum % p);
			sum = 1ll * sum * i % p;
			x = i & 1, i >>= 1;
		}
		return;
	}else{
		dfs2(i << 1, sum), dfs2(i << 1 | 1, sum);
	}
}

int main(){
	scanf("%d", &h), l = 1 << (h - 1);
	for(int i = 1;i <= l;i++) scanf("%d", &P[i]);
	for(int i = 1;i < l;i++){
		dfs1(i << 1, i), dfs2(i << 1 | 1, 1);
		while(top){
			int x = sk[top--];
			while(x) a[x >> 1][x & 1] = 0, x >>= 1;
		}
	}
	printf("%d", ans);
}