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 comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
  
#include <iostream>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <assert.h>
#include <memory.h>
#include <time.h>
#include <bitset>

#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define ld long double
#define rep(i, l, r) for (int i = (l); i < (r); i++)
#define repb(i, r, l) for (int i = (r); i > (l); i--)
#define sz(a) (int)a.size()
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define rank qwertyuio
#define next dfghjk
#define prev fhsgfhjf
#define plus fsghsf
#define minus ytryr
  
using namespace std;
  
inline bool setmin(int &x, int y) { return (y < x) ? x = y, 1 : 0; }
inline bool setmax(int &x, int y) { return (y > x) ? x = y, 1 : 0; }
inline bool setmin(ll &x, ll y) { return (y < x) ? x = y, 1 : 0; }
inline bool setmax(ll &x, ll y) { return (y > x) ? x = y, 1 : 0; }
  
const int N = 18;
const int inf = (int)1e9 + 1;
const ll big = (ll)1e18 + 1;
const int P = 239;
const int P1 = 31;
const int P2 = 57;
const int MOD = (int)1e9 + 7;
const int MOD1 = (int)1e9 + 9;
const int MOD2 = 998244353;
const ld eps = 1e-9;
const double pi = atan2(0, -1);
const int ABC = 26;

inline void add(int &x, int y) {
    x += y;
    if (x >= MOD) {
        x -= MOD;
    }
}

int H;

int perm[(1 << (N - 1)) + 239];

int sum_paths[N + 1][(1 << N) + 239];
int acc_id[N + 1][(1 << N) + 239];
vector<int> leaves[N + 1];

inline void add_val(int p, int id, int x, int val) {
    if (acc_id[p][x] != id) {
        acc_id[p][x] = id;
        sum_paths[p][x] = 0;
    }
    add(sum_paths[p][x], val);
}

inline int get_val(int p, int id, int x) {
    return acc_id[p][x] == id ? sum_paths[p][x] : 0;
}

int ans = 0;

queue<int> Q;

void init() {
    rep(i, 0, N + 1) {
        Q.push(i);
    }
}

int solve(int x) {
    if (x * 2 >= (1 << H)) {
        int p = Q.front(); Q.pop();
        leaves[p].clear();
        int u = (1 << (H - 1)) + perm[x - (1 << (H - 1))];
        leaves[p].push_back(u);
        ll val = x;
        while (u > 0) {
            val = val * u % MOD;
            add_val(p, x, u, val);
            u /= 2;
        }        
        return p;
    }
    int p_L = solve(x * 2), p_R = solve(x * 2 + 1);
    int p = Q.front(); Q.pop();
    leaves[p].clear();
    int i1 = 0, i2 = 0;
    while (i1 < sz(leaves[p_L]) || i2 < sz(leaves[p_R])) {
        if (i2 == sz(leaves[p_R]) || (i1 < sz(leaves[p_L]) && leaves[p_L][i1] <= leaves[p_R][i2])) {
            if (sz(leaves[p]) == 0 || leaves[p_L][i1] != leaves[p].back()) {
                leaves[p].push_back(leaves[p_L][i1]);
            }
            i1++;
        } else {
            if (sz(leaves[p]) == 0 || leaves[p_R][i2] != leaves[p].back()) {
                leaves[p].push_back(leaves[p_R][i2]);
            }
            i2++;
        }
    }
    for (int leaf : leaves[p]) {
        int u = leaf;
        while (u > 0) {
            if (acc_id[p][u] == x) {
                u /= 2;
                continue;
            }
            add_val(p, x, u, 1LL * get_val(p_L, x * 2, u) * x % MOD);
            add_val(p, x, u, 1LL * get_val(p_R, x * 2 + 1, u) * x % MOD);
            if (u * 2 < (1 << H)) {
                ll val = 1LL * get_val(p_L, x * 2, u * 2) * get_val(p_R, x * 2 + 1, u * 2 + 1) % MOD;
                val = val * u % MOD * x % MOD;
                add(ans, val);

                //cout << x << " " << u << " " << 1 << " " << val << endl;

                val = 1LL * get_val(p_L, x * 2, u * 2 + 1) * get_val(p_R, x * 2 + 1, u * 2) % MOD;
                val = val * u % MOD * x % MOD;
                add(ans, val);

                //cout << x << " " << u << " " << 2 << " " << val << endl;
            }

            u /= 2;
        }
    }
    /*cout << x << ":\n";
    for (int i = 1; i < (1 << H); i++) {
        cout << get_val(p, x, i) << " ";
    }
    cout << "\n";*/
    Q.push(p_L);
    Q.push(p_R);
    //cout << x << " " << ans << endl;
    return p;
}

int main()
{
    //freopen("circus.in", "r", stdin);
    //freopen("circus.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.precision(20);
    cout << fixed;
    //ll TL = 10.95 * CLOCKS_PER_SEC;
    //clock_t time = clock();
    init();
    cin >> H;
    rep(i, 0, 1 << (H - 1)) {
        cin >> perm[i];
        perm[i]--;
    }
    solve(1);
    cout << ans << "\n";
    return 0;
}

