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 pb push_back
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int N=1e6+50,mod=1e9+7;
int h,lim,p[N],cnt,dat[N],inv[N],idat[N],sum[N],ans;
vector<pii>v[N];
int read(){
    int x=0,c;
    while(!isdigit(c=getchar()));
    while(isdigit(c))x=x*10+c-48,c=getchar();
    return x;
}
int main(){
    scanf("%d",&h);lim=1<<h;cnt=lim>>1;
    inv[1]=1;
    for(int i=2;i<lim;i++)
        inv[i]=mod-1ll*mod/i*inv[mod%i]%mod;
    for(int i=cnt,x;i<lim;i++)v[i].pb(mp(i,read()+cnt-1));
    dat[1]=idat[1]=1;
    for(int i=2;i<lim;i++)
        dat[i]=1ll*dat[i>>1]*i%mod,
        idat[i]=1ll*idat[i>>1]*inv[i]%mod;
    for(int i=1;i<lim;i++)idat[i]=1ll*i*idat[i]%mod*idat[i]%mod;
    for(int i=cnt-1;i;i--){
        v[i]=v[i<<1];
        for(int j=0;j<v[i<<1|1].size();j++)
            v[i].pb(v[i<<1|1][j]);
    }
    for(int i=1;i<cnt;i++){
        for(int j=0;j<v[i<<1].size();j++){
            int x=v[i<<1][j].first,y=v[i<<1][j].second,yy=y;
            while(y)sum[y]=(sum[y]+1ll*dat[x]*idat[i]%mod*dat[yy])%mod,y>>=1;
        }
        for(int j=0;j<v[i<<1|1].size();j++){
            int x=v[i<<1|1][j].first,y=v[i<<1|1][j].second,yy=y;
            int tmp=0;
            while(y)tmp=(tmp+1ll*sum[y]*(idat[y]-idat[y>>1]))%mod,y>>=1;
            ans=(ans+1ll*tmp*dat[yy]%mod*dat[x])%mod;
        }
        for(int j=0;j<v[i<<1].size();j++){
            int y=v[i<<1][j].second;while(y)sum[y]=0,y>>=1;
        }
    }
    cout<<ans;
    return 0;
}
