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 sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<lint, lint> pi;
const int MAXN = 530000;
const int mod = 1e9 + 7;

struct mint {
    int val;
    mint() { val = 0; }
    mint(const lint& v) {
        val = (-mod <= v && v < mod) ? v : v % mod;
        if (val < 0) val += mod;
    }

    friend ostream& operator<<(ostream& os, const mint& a) { return os << a.val; }
    friend bool operator==(const mint& a, const mint& b) { return a.val == b.val; }
    friend bool operator!=(const mint& a, const mint& b) { return !(a == b); }
    friend bool operator<(const mint& a, const mint& b) { return a.val < b.val; }

    mint operator-() const { return mint(-val); }
    mint& operator+=(const mint& m) { if ((val += m.val) >= mod) val -= mod; return *this; }
    mint& operator-=(const mint& m) { if ((val -= m.val) < 0) val += mod; return *this; }
    mint& operator*=(const mint& m) { val = (lint)val*m.val%mod; return *this; }
    friend mint ipow(mint a, lint p) {
        mint ans = 1; for (; p; p /= 2, a *= a) if (p&1) ans *= a;
        return ans;
    }
    friend mint inv(const mint& a) { assert(a.val); return ipow(a, mod - 2); }
    mint& operator/=(const mint& m) { return (*this) *= inv(m); }

    friend mint operator+(mint a, const mint& b) { return a += b; }
    friend mint operator-(mint a, const mint& b) { return a -= b; }
    friend mint operator*(mint a, const mint& b) { return a *= b; }
    friend mint operator/(mint a, const mint& b) { return a /= b; }
    operator int64_t() const {return val; }
};

int n, a[MAXN];

struct foo{
	mint asum, bsum, tot;
}dp[MAXN];

foo merge(foo a, foo b, int v){
	foo ret;
	ret.asum = mint(v) * (a.asum + b.asum);
	ret.bsum = mint(v) * (a.bsum + b.bsum);
	ret.tot = a.tot + b.tot + mint(v) * (a.asum * b.bsum + a.bsum * b.asum);
	return ret;
}

void setDP(int x, mint p, mint q){
	x += (1<<(n-1)) - 1;
	dp[x] = (foo){p * mint(x), q * mint(x), 0};
	while(x > 1){
		x >>= 1;
		dp[x] = merge(dp[2*x], dp[2*x+1], x);
	}
}

mint getPath(int x, int y){
	mint ret = 1;
	while(x > y){
		ret *= mint(x);
		x /= 2;
	}
	assert(x == y);
	return ret;
}

mint solve(int s, int e, int p){
	if(s == e) return mint(0);
	int m = (s+e)/2;
	mint ret = solve(s, m, 2*p) + solve(m + 1, e, 2*p+1);
	for(int i=s; i<=m; i++){
		setDP(a[i], getPath(i + (1<<(n-1)) - 1, p) * mint(p), mint(0));
	}
	for(int i=m+1; i<=e; i++){
		setDP(a[i], mint(0), getPath(i + (1<<(n-1)) - 1, p));
	}
	ret += dp[1].tot;
	for(int i=s; i<=e; i++) setDP(a[i], mint(0), mint(0));
	return ret;
}

int main(){
	scanf("%d",&n);
	for(int i=1; i<=(1<<(n-1)); i++) scanf("%d",&a[i]);
	cout << solve(1, (1<<(n-1)), 1) << endl;
}
