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
#pragma GCC optimize("O3")   //
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, b, a) for(int i = b - 1; i >= a; i--)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef long double ld;
typedef unsigned long long ull;

unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
std::mt19937 eng(seed);

uniform_int_distribution<> DD(0, (1ll << 31));

ll random2(){
    return (ll(DD(eng))*(1ll << 31) + ll(DD(eng))) & ((1ll << 62ll)-1);
}

ll n,m,k,q,T;

const ll big = 1000000007;
const ll big2 = 1000000009;
const ll mod =  998244353;

const int MAXN = 300001;

ll h;

struct pt{
    ll x,y;
};

vi P;


ll PROD[MAXN][20] = {0};

int pp(ll i){
    return P[i-(1 << (h-1))] + (1 << (h-1));
}

ll C[MAXN] = {0};
int CC1[MAXN] = {0};
int cc1 = 0;
vi NEW1 = {0};
void reset(){
    trav(i,NEW1){
        C[i] = 0;
    }
    cc1++;
    NEW1.clear();
}

void add(ll p, ll to){
    C[to] += p;
    C[to] %= big;
    if(CC1[to] != cc1){
        CC1[to] = cc1;
        NEW1.push_back(to);
    }
    //cerr << "ADD: "  << p << " to: " << to << "\n";
}

void dfs(ll i, ll p, int start){
    while(i > 0){
        p *= i;
        p %= big;
        if(i > 1){
            ll other = (i/2)*2;
            if(other == i)other++;
            add((p*(i/2)), other);
        }

        if(i == 1)return;
        i /= 2;
    }
}

void setup(ll i, ll p){
    ll jj = i;
    ll nums = 1;
    ll b = 0;
    while(jj < (1 << (h-1))){
        jj *= 2;
        nums *= 2;
        b++;
    }

    rep(c1,0,nums){
        dfs(pp(jj+c1), PROD[jj+c1][b], i);
    }

}


int CC2[MAXN] ={0};
int cc2 = 0;

ll solve(ll i){
    reset();
    setup(2*i+1,1);
    ll j = i;

    ll nums = 1;
    while(j < (1 << (h-1))){
        j *= 2;
        nums *= 2;
    }
    nums /= 2;

    ll ans = 0;

    ll ppp = 0;
    ll jjj = i;
    while(jjj < (1 << (h-1))){
        jjj*=2;
        ppp++;
    }

    for(ll c1 = 0; c1 < nums; c1++){
        ll j2 = j+c1;
        cc2++;
        ll prod = 1;
        ll j3 = j2;

        prod = PROD[j3][ppp];

        j3 = pp(j2);

        while(j3 > 0){

           prod *= j3;
            prod %= big;
            ans += prod*C[j3];
            ans %= big;
            j3 /= 2;
        }

    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    //freopen("input.txt","r",stdin);
    //freopen("autput.txt","w",stdout);

    ll a,b,c,d,e;

    cin >> h;
    n = (1 << h)+1;


    for(ll c1 = 1; c1 < (1 << h)+1; c1++){
        ll p = c1;
        ll c2 = c1;
        PROD[c1][0] = p;
        for(ll c3 = 1; c3 < 20; c3++){
            c2 /= 2;
            p *= c2;
            p %= big;
            PROD[c1][c3] = p;
        }
    }

    rep(c1,0,(1 << (h-1))){
        cin >> a;
        //a = c1+1;
        P.push_back(a-1);
    }

    ll ans = 0;
    rep(c1,1,(1 << (h-1))){
        ans += solve(c1);
        ans %= big;
    }

    cout << ans << "\n";

    return 0;
}
