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 rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define FI first
#define SE second
#define maxn (1<<18)
#define mod 1000000007
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef double db;

int dep[maxn+5];
int per[maxn+5];
ll sum[maxn+5];

int main()
{
    int H; scanf("%d",&H);
    int n=1<<(H-1),base=n-1;
    rep(i,1,base+n) dep[i]=dep[i/2]+1;
    rep(i,1,n) scanf("%d",&per[base+i]),per[base+i]+=base;
    ll ans=0;
    rep(now,1,base)
    {
        //int ls=now*2,rs=now*2+1;
        int N=1<<(H-dep[now]-1);
        int L=now<<(H-dep[now]),R=L+N;
        rep(x,L,L+N-1)
        {
            ll mul=1;
            int tmp=x;
            while(tmp>=now)
            {
                mul=mul*tmp%mod;
                tmp>>=1;
            }
            int y=per[x];
            while(y)
            {
                mul=mul*y%mod;
                sum[y]=(sum[y]+mul)%mod;
                //printf("?? %d, %d: %lld\n",x,y,mul);
                y>>=1;
            }
        }
        rep(x,R,R+N-1)
        {
            ll mul=1;
            int tmp=x;
            while(tmp>now)
            {
                mul=mul*tmp%mod;
                tmp>>=1;
            }
            int y=per[x];
            while(y>1)
            {
                //printf("-- %d, %d: %lld, %lld\n",x,y,mul,sum[y]*mul%mod);
                mul=mul*y%mod;
                ans=(ans+(sum[y/2]-sum[y]*(y/2)%mod+mod)*mul)%mod;
                y>>=1;
            }
        }
        rep(x,L,L+N-1)
        {
            int y=per[x];
            while(y)
            {
                sum[y]=0;
                y>>=1;
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}