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<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<complex>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define INF (1<<29)
#define LINF (1LL<<60)
#define EPS (1e-10)
#define PI 3.1415926535897932384626433832795028
typedef long long Int;
typedef pair<Int, Int> P;
typedef long double Real;
typedef complex<Real> CP;

Int n, x;
vector<Int> other[1 << 18];
vector<Int> children[1 << 18];
Int sum[1 << 18];
Int cnt[1 << 18];
Int prod[1 << 18];
Int parent[1 << 18];
Int cost[1 << 18];
Int val[1 << 18];
Int top[1 << 18];
Int all_sum[1 << 18];
Int ans;

Int mod_pow(Int x, Int a, Int m = MOD){
    if(a == 0)return 1;
    if(a % 2 == 1)return x * mod_pow(x, a - 1, m) % m;
    Int res = mod_pow(x, a / 2, m);
    return res * res % m;
}

Int inv(Int x, Int m = MOD){
    return mod_pow(x, m-2, m);
}


Int lca(Int x, Int y){
    Int diff = top[x ^ y] * 2;
    return x / diff;    
}

int main(){
    cin >> n;
    Int base = 1 << (n-1);
    prod[1] = 1;
    top[1] = 1;
    for(Int i = 2;i < (1 << 18);i++){
        prod[i] = prod[i/2] * i % MOD;
        top[i] = top[i/2] * 2;
    }    
    for(Int i = 0;i < base;i++){
        cin >> x;x--;
        sum[x + base] = prod[x + base] * prod[i + base] % MOD;
        Int now = i + base;
        while(now > 0){
            other[now].push_back(x + base);
            now /= 2;
        }
    }
    for(Int i = base-1;i > 0;i--){
        sort(other[i].begin(), other[i].end());
        vector<Int> right_most = {other[i][0]};        
        vector<Int> nodes = other[i];
        for(Int j = 1;j < other[i].size();j++){
            Int l = lca(other[i][j-1], other[i][j]);
            Int last_out = -1;
            while(!right_most.empty() && right_most.back() > l){
                last_out = right_most.back();
                right_most.pop_back();
            }
            parent[other[i][j]] = l;
            if(!right_most.empty() && right_most.back() == l){
                right_most.push_back(other[i][j]);
                continue;
            }
            nodes.push_back(l);
            if(!right_most.empty())parent[l] = right_most.back();
            else parent[l] = -1;
            sum[l] = 0;
            children[l].clear();
            if(last_out != -1)parent[last_out] = l;
            right_most.push_back(l);
            right_most.push_back(other[i][j]);
        }
        sort(nodes.rbegin(), nodes.rend());
        for(auto v: nodes){           
            if(parent[v] == -1)continue;
            Int p = parent[v];
            children[p].push_back(v);       
            (sum[p] += sum[v]) %= MOD;
        }
        for(auto v: nodes){            
            if(children[v].empty())continue;
            if(children[v].size() != 2)return -1;
            Int a = sum[children[v][0]] * inv(prod[v]) % MOD;
            Int b = sum[children[v][1]] * inv(prod[v])  % MOD;
            (all_sum[i] += a * b % MOD * v % MOD) %= MOD;
        }
    }
    for(Int i = 1;i < base;i++){
        (all_sum[i] -= all_sum[i*2] + all_sum[i*2+1]) %= MOD;
        (all_sum[i] *= inv(prod[i])) %= MOD;
        (all_sum[i] *= inv(prod[i])) %= MOD;
        (ans += all_sum[i] * i % MOD) %= MOD;
    }
    if(ans < 0)ans += MOD;
    cout << ans << endl;
    return 0;
}