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
#define DEBUG 0

#include <bits/stdc++.h>
using namespace std;

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------
#define MOD 1000000007

int H,L[1 << 17];
LLI P[1 << 17];
int l[1 << 18],r[1 << 18];
LLI inv(LLI n) {
    LLI r = 1;
    int e = MOD-2;
    while (e > 0) {
        if (e & 1) r *= n,r %= MOD;
        e >>= 1;
        n *= n,n %= MOD;
    }
    return r;
}
LLI prea[1 << 19],preb[1 << 19];
LLI query(vi &v,int l,int r,int t) {
    r = upper_bound(v.begin(),v.end(),r)-v.begin()-1;
    l = lower_bound(v.begin(),v.end(),l)-v.begin();
    if (l <= r) {
        if (t == 0) return prea[r+1]-prea[l];
        else return preb[r+1]-preb[l];
    }
    else return 0;
}
LLI findAns2(vi a,vi b) {
    printArr(a,a.size());
    printArr(b,b.size());
    int i,j;
    vi v;
    vpii lca;
    LLI ans = 0;
    for (i = 0; i < a.size(); i++) v.pb(L[a[i]]);
    for (i = 0; i < b.size(); i++) v.pb(L[b[i]]);
    sort(v.begin(),v.end());
    fill(prea,prea+v.size()+1,0);
    fill(preb,preb+v.size()+1,0);
    for (i = 0; i < a.size(); i++) {
        int p = lower_bound(v.begin(),v.end(),L[a[i]])-v.begin();
        prea[p+1] += (P[a[i]]*P[L[a[i]]]) % MOD,prea[p] %= MOD;
    }
    for (i = 0; i < b.size(); i++) {
        int p = lower_bound(v.begin(),v.end(),L[b[i]])-v.begin();
        preb[p+1] += (P[b[i]]*P[L[b[i]]]) % MOD,preb[p] %= MOD;
    }
    for (i = 0; i < v.size(); i++) {
        prea[i+1] = (prea[i+1]+prea[i]) % MOD;
        preb[i+1] = (preb[i+1]+preb[i]) % MOD;
    }
    printArr(v,v.size());
    for (i = 1; i < v.size(); i++) {
        LLI p = 1,c = 1;
        for (j = H-2; j >= 0; j--) {
            if ((v[i]^v[i-1]) & (1 << j)) break;
            else {
                if (v[i] & (1 << j)) p *= c,c = 2*c+1,p %= MOD;
                else p *= c,c = 2*c,p %= MOD;
            }
        }
        debug p,c;
        LLI x = (query(v,l[c],r[c],0)*query(v,l[c],r[c],1)) % MOD;
        LLI y = (query(v,l[2*c],r[2*c],0)*query(v,l[2*c],r[2*c],1)) % MOD;
        LLI z = (query(v,l[2*c+1],r[2*c+1],0)*query(v,l[2*c+1],r[2*c+1],1)) % MOD;
        debug x,y,z;
        ans += ((x-y-z)*inv((((p*p) % MOD)*c) % MOD)) % MOD;
    }
    ans %= MOD;
    if (ans < 0) ans += MOD;
    printVar(ans);
    return ans;
}
int findAns(vi v,int t,LLI p) {
    if (v.size() == 1) return 0;
    int i;
    vi l,r;
    for (i = 0; i < v.size()/2; i++) l.pb(v[i]);
    for (i = v.size()/2; i < v.size(); i++) r.pb(v[i]);
    LLI ans = findAns(l,2*t,(p*t) % MOD)+findAns(r,2*t+1,(p*t) % MOD);
    LLI ans2 = (findAns2(l,r)*inv((((p*p) % MOD)*t) % MOD)) % MOD;
    printVar(ans2);
    return (ans+ans2) % MOD;
}
int main() {
    int i;
    vi v;
    scanf("%d",&H);
    for (i = 0; i < (1 << (H-1)); i++) scanf("%d",&L[i]),L[i]--,v.pb(i);

    int j;
    memset(l,-1,sizeof(l));
    memset(r,-1,sizeof(r));
    for (i = 0; i < (1 << (H-1)); i++) {
        P[i] = 1;
        int c = i+(1 << (H-1));
        if (l[c] == -1) l[c] = r[c] = i;
        else l[c] = min(l[c],i),r[c] = max(r[c],i);
        for (j = 0; j < H; j++) {
            P[i] *= c,P[i] %= MOD,c /= 2;
            if (l[c] == -1) l[c] = r[c] = i;
            else l[c] = min(l[c],i),r[c] = max(r[c],i);
        }
    }
    printf("%d\n",findAns(v,1,1));

    return 0;
}

