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>
#ifndef LOCAL_PROJECT
#define cerr if(0)cerr
#endif
using namespace std;
typedef pair<int,int>pii;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef __int128 lll;
const lll ONE=1;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
const int mn=2e6+10;
const ll inf=0x3f3f3f3f3f3f3f3f;
const ll mod=1e9+7;

int h;
int p[mn];
ll val[mn];
ll ans=0;
void hail(vector<int>&o,int l,int r,bool b,int par){
    int mid=(l+r)>>1;
    vector<pll>v;
    for(int i=l;i;i>>=1)v.push_back({i,0});
    reverse(v.begin(),v.end());
    for(int i:o){
        for(int j=p[i];j!=v.back().first;j>>=1){
            v[v.size()-2].second+=v.back().first*v.back().second%mod;
            v[v.size()-2].second%=mod;
            v.pop_back();
        }
        for(int j=h-1;j>=0;j--)if(p[i]>>j>v.back().first)v.push_back({p[i]>>j,0});
        if((i<=mid)^b){
            v.back().second+=val[i];
            v.back().second%=mod;
        }
        else{
            ll ad=val[i]*par%mod;
            for(int j=v.size()-1;j>=0;j--){
                ad*=v[j].first,ad%=mod;
                ans+=ad*v[j].second%mod,ans%=mod;
            }
        }
    }
}
void solve(int l,int r,int par){
    if(l==r)return;
    int mid=(l+r)>>1;
    for(int i=l;i<=r;i++){
        val[i]=1;
        for(int j=i;j>par;j>>=1)val[i]*=j,val[i]%=mod;
    }
    vector<int>o(r-l+1);
    iota(o.begin(),o.end(),l);
    sort(o.begin(),o.end(),[](int a,int b){return p[a]<p[b];});
    hail(o,l,r,0,par);
    hail(o,l,r,1,par);
    solve(l,mid,par*2);
    solve(mid+1,r,par*2+1);
}
int main(){
#ifdef LOCAL_PROJECT
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    freopen("error.txt","w",stderr);
#else
    cin.tie(0);
    cin.sync_with_stdio(0);
#endif
    cin>>h;
    for(int i=1<<h-1;i<1<<h;i++){
        cin>>p[i];
        p[i]+=(1<<h-1)-1;
    }
    solve(1<<h-1,(1<<h)-1,1);
    printf("%lld",ans);
}



