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 REP(i,a,b) for(int i=(a),_ed_=(b);i<=_ed_;++i)
#define DREP(i,a,b) for(int i=(a),_ed_=(b);i>=_ed_;--i)
#define pb push_back
#define mp make_pair
#define sz(x) (int)((x).size())
typedef long long ll;
typedef pair<int,int> pii;
inline int read(){
    register int x=0,f=1;register char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
    while(isdigit(ch)){x=x*10+(ch^'0');ch=getchar();}
    return f?x:-x;
}

const int P=1000000007;
void inc(int& x,int y){x=x+y<P?x+y:x+y-P;}

int h,n,p[600005],ans;

int tr[600005];
void insert(int x,int w){while(x)w=1ll*w*x%P,inc(tr[x],w),x>>=1;}
void del(int x){while(x)tr[x]=0,x>>=1;}
int query(int x,int w){
    int res=0,ans=0;
    while(x){
	int t=(P+tr[x]-1ll*res*x%P)%P;
	inc(ans,1ll*t*w%P);
	res=tr[x],w=1ll*w*x%P,x>>=1;
    }
    return ans;
}

vector<pii> dfs(int u){
    vector<pii> L,R;
    if(u>n+n-1)return L;
    L=dfs(u<<1),R=dfs(u<<1|1);
    for(pii nw:L)insert(p[nw.first],1ll*nw.second*u%P);
    for(pii nw:R)inc(ans,query(p[nw.first],nw.second));
    for(pii nw:L)del(p[nw.first]);
    L.insert(L.end(),R.begin(),R.end());
    REP(i,0,sz(L)-1)L[i].second=1ll*L[i].second*u%P;
    if(!sz(L))L.pb(mp(u,u));
    return L;
}

int main(){
    //freopen("in.in","r",stdin);
    h=read();n=1<<(h-1);
    REP(i,n,n+n-1)p[i]=n+read()-1;
    dfs(1);
    printf("%d\n",ans);
    return 0;
}
