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;
typedef long long ll;
const int maxh=18;
const int maxn=(1<<maxh)|1;
const int kcz=1000000007;
int h,n,L,p[maxn],sz[maxn],dfn[maxn],clk,tp[maxn],temp[maxn],top,sta[maxn];
ll val[maxn],invval[maxn],ans,cur[maxn],tot[maxn][2];
inline int LCA(int x,int y)
{
    int i;
    for(i=0;(x^y)>>(i+1);i++);
    return (x&y)>>(i+1);
}
inline bool cmp(int x,int y) { return dfn[x]<dfn[y]; }
void solve(int l,int r,int lca)
{
    if(l==r) return;
    int mid=(l+r)>>1,i,t;
    solve(l,mid,lca<<1),solve(mid+1,r,(lca<<1)|1);
    for(i=l;i<=r;i++) temp[i-l]=p[i],tp[p[i]]=i<=mid,cur[p[i]]=val[i]*invval[lca>>/*1*/tp[p[i]]]%kcz*val[p[i]]%kcz;
    // for(i=l;i<=r;i++) printf("%lld ",cur[p[i]]); printf("\n");
    sort(temp,temp+r-l+1);
    t=r-l+1;
    for(i=1;i<=r-l;i++) temp[t++]=LCA(temp[i-1],temp[i]);
    sort(temp,temp+t,cmp);
    // printf("%lld\n",ans); for(i=0;i<t;i++) printf("%d ",temp[i]); printf("\n");
    for(i=0,top=-1;i<t;i++)
    {
        while(top>=0 && (dfn[sta[top]]>dfn[temp[i]] || dfn[sta[top]]+sz[sta[top]]<=dfn[temp[i]]))
        {
            if(top)
            {
                (ans+=(tot[top][0]*tot[top-1][1]+tot[top][1]*tot[top-1][0])%kcz*invval[sta[top-1]>>1]%kcz*invval[sta[top-1]])%=kcz;
                (tot[top-1][0]+=tot[top][0])%=kcz,(tot[top-1][1]+=tot[top][1])%=kcz;
            }
            top--;
        }
        top++;
        sta[top]=temp[i],tot[top][0]=tot[top][1]=0;
        if(L&temp[i]) tot[top][tp[temp[i]]]=cur[temp[i]];
    }
    while(top>0)
    {
        (ans+=(tot[top][0]*tot[top-1][1]+tot[top][1]*tot[top-1][0])%kcz*invval[sta[top-1]>>1]%kcz*invval[sta[top-1]])%=kcz;
        (tot[top-1][0]+=tot[top][0])%=kcz,(tot[top-1][1]+=tot[top][1])%=kcz;
        top--;
    }
}
void dfs(int u)
{
    if(u>=n) return;
    dfn[u]=clk++;
    dfs(u<<1),dfs((u<<1)|1);
}
int main()
{
    int i;
    scanf("%d",&h),L=1<<(h-1),n=1<<h;
    for(i=L;i<n;i++) scanf("%d",&p[i]),p[i]+=L-1;
    for(invval[0]=invval[1]=1,i=2;i<n;i++)
        invval[i]=kcz-(kcz/i)*invval[kcz%i]%kcz;
    for(val[1]=1,i=2;i<n;i++)
        val[i]=i*val[i/2]%kcz,(invval[i]*=invval[i/2]%kcz)%=kcz;
    for(i=1;i<n;i++) sz[i]=0;
    for(i=n-1;i;i--) sz[i]++,sz[i>>1]+=sz[i];
    clk=0,dfs(1);
    // for(i=1;i<n;i++) printf("%d ",dfn[i]); printf("\n");
    ans=0,solve(L,n-1,1);
    printf("%lld\n",ans);
    return 0;
}