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;

#define ll long long
#define sd(x) scanf("%d", &(x))
#define pii pair<int, int>
#define F first
#define S second
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#define ld long double

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<", "<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"{";
	for(int i = 0;i < (int)v.size(); i++){
		if(i)os<<", ";
		os<<v[i];
	}
	os<<"}";
	return os;
}

#ifdef LOCAL
#define cerr cout
#else
#endif

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

const int mod = 1e9 + 7;
inline int add(int x, int y){ x += y; if(x >= mod) x -= mod; return x;}
inline int sub(int x, int y){ x -= y; if(x < 0) x += mod; return x;}
inline int mul(int x, int y){ return (x * 1ll * y) % mod;}
inline int powr(int a, ll b){
	int x = 1 % mod;
	while(b){
		if(b & 1) x = mul(x, a);
		a = mul(a, a);
		b >>= 1;
	}
	return x;
}
inline int inv(int a){ return powr(a, mod - 2);}
const int H = 18;
const int N = 1 << H;
int f[N], p[N], invf[N];

struct BIT{
	int * F;
	BIT(){
        F = new int[N];
    };
	void update(int i, int w){
		for(; i < N; i += (i & (-i))) F[i] = add(F[i], w);
	}
	int get(int i){
		int ret = 0;
		for(; i; i -=(i & (-i))) ret = add(ret, F[i]);
		return ret;
	}
	int get(int i, int j){ return sub(get(j), get(i - 1));}
};

BIT bit;

int st[N], en[N], isLeaf[N], g[N], RR[N], hgt[N];
int timer = 0;
void dfs(int s, int h){
    if(h == 0) return;
    hgt[s] = h - 1;
    st[s] = ++timer;
    isLeaf[s] = h == 1;
    f[s] = mul(s, f[s >> 1]);
    invf[s] = inv(f[s]);
    g[s] = mul(invf[s], mul(s, invf[s]));
    dfs(2 * s, h - 1);
    dfs(2 * s + 1, h - 1);
    en[s] = timer;
}

int main(){
    int h; sd(h);
    int L = (1 << (h - 1));
    int n = 2 * L - 1;
    for(int i = 1; i <= L; i++) sd(p[i]);
    f[0] = 1;
    dfs(1, h);

    for(int i = L; i <= n; i++){
        RR[i] = mul(f[i], f[p[i - L + 1] + L - 1]);
    }

    int ans = 0;

    for(int l = 1; l < L; l++){
        int a = 2 * l, b = 2 * l + 1;
        int P = a << hgt[a], Q = (b << hgt[b]), R = ((b + 1) << hgt[b]) - 1;
        for(int u = Q; u <= R; u++) if(isLeaf[u]){
            int _u = p[u - L + 1] + L - 1;
            bit.update(st[_u], RR[u]);
        }
        for(int u = P; u < Q; u++) if(isLeaf[u]){
            int coeff = mul(RR[u], g[l]);
            int sm = 0;
            int _u = p[u - L + 1] + L - 1;
            int old = _u;
            int _l = _u >> 1;
            while(_l){
                int sibling = old ^ 1;
                int here = bit.get(st[sibling], en[sibling]);
                sm = add(sm, mul(g[_l], here));
                old =_l;
                _l >>= 1;
            }
            ans = add(ans, mul(coeff, sm));
        }
        for(int u = Q; u <= R; u++) if(isLeaf[u]){
            int _u = p[u - L + 1] + L - 1;
            bit.update(st[_u], sub(0, RR[u]));
        }
    }
    printf("%d\n", ans);
}