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>
using namespace std;
 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse4")
 
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
 
#define SZ(a) (int)((a).size())
#define ALL(a) a.begin(), a.end()
 
typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1000 * 1000 * 1000 + 7;
const int LOG = 18;
const int MAX = 1 << LOG;

void updAdd(int& x, int val)
{
	x += val;
	if(x >= mod)
		x -= mod;
}

int mult(int a, int b)
{
	return (LL)a * b % mod;
}

int p[MAX];
int inv[MAX];
int f[MAX], g[MAX];
vector<int> vec[MAX];
int last[MAX][LOG];
int ptr[MAX][LOG], sum[MAX][LOG];

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int h;
	cin >> h;
	inv[1] = f[1] = g[1] = 1;
	FOR(i, 2, 1 << h)
	{
		inv[i] = mult(inv[mod % i], mod - mod / i);
		f[i] = mult(i, f[i >> 1]);
		g[i] = mult(inv[i], g[i >> 1]);
	}
	FOR(i, 1, 1 << h)
		g[i] = mult(i, mult(g[i], g[i]));
	int l = 1 << (h - 1);
	FOR(i, 0, l)
	{
		cin >> p[i];
		p[i]--;
		int v = l + p[i];
		while(v)
		{
			vec[v].push_back(i);
			v >>= 1;
		}
	}
	FOR(i, 1, 1 << h)
		FOR(j, 0, h)
			last[i][j] = -1;
	int ans = 0;
	FOR(i, 0, l)
	{
		int s2 = 0;
		for(int v = l + p[i]; v > 1; v >>= 1)
		{
			int s1 = 0;
			for(int u = l + i, du = h - 1; du; u >>= 1, du--)
			{
				if(!(u & 1))
				{
					if(last[v ^ 1][du] < (u ^ 1))
					{
						sum[v ^ 1][du] = 0;
						while(ptr[v ^ 1][du] < SZ(vec[v ^ 1]) && ((l + vec[v ^ 1][ptr[v ^ 1][du]]) >> (h - 1 - du)) <= (u ^ 1))
						{
							if(((l + vec[v ^ 1][ptr[v ^ 1][du]]) >> (h - 1 - du)) == (u ^ 1))
								updAdd(sum[v ^ 1][du],
									mult(f[l + vec[v ^ 1][ptr[v ^ 1][du]]], f[l + p[vec[v ^ 1][ptr[v ^ 1][du]]]]));
							ptr[v ^ 1][du]++;
						}
						last[v ^ 1][du] = u ^ 1;
					}
					updAdd(s1, mult(g[u >> 1], sum[v ^ 1][du]));
				}
			}
			updAdd(s2, mult(g[v >> 1], s1));
		}
		updAdd(ans, mult(mult(f[l + i], f[l + p[i]]), s2));
	}
	cout << ans << "\n";
	return 0;
}
