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 mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

const int maxn = 1 << 18;
const i64 P = 1000000000 + 7;

i64 deg(i64 x, i64 d) {
    if (d < 0) d += P - 1;
    i64 y = 1;
    while (d) {
        if (d & 1) (y *= x) %= P;
        d /= 2;
        (x *= x) %= P;
    }
    return y;
}

int perm[maxn];
i64 path[maxn], lcac[maxn];

int h, off;

pi64 operator+(pi64 a, pi64 b) {
    return {(a.fi + b.fi) % P, (a.se + b.se) % P};
}

pi64 operator-(pi64 a, pi64 b) {
    return {(a.fi - b.fi) % P, (a.se - b.se) % P};
}

pi64 operator*(pi64 a, i64 t) {
    return {a.fi * t % P, a.se * t % P};
}

i64 cross(pi64 a, pi64 b) {
    return (a.fi * b.se + a.se * b.fi) % P;
}

int len(int u) {
    return 32 - __builtin_clz(u);
}

int lca(int u, int v) {
    int ub = min(len(u), len(v));
//    cerr << u << ' ' << v << " -> ";
    u <<= 31 - len(u);
    v <<= 31 - len(v);
    int com = __builtin_clz(u ^ v) - 1;
    uin(com, ub);
//    cerr << (u >> (len(u) - com)) << '\n';
    return u >> (len(u) - com);
}

i64 solve(int i, int b) {
    if (b == 0) return 0;
    vector<pair<int, pi64> > a(1 << b);
    forn(j, 1 << b) {
        pi64 w;
        (j < (1 << (b - 1)) ? w.fi : w.se) = path[off + i + j] * path[off + perm[i + j]] % P;
        a[j] = mp(perm[i + j] + off, w);
    }
    sort(all(a));
    pi64 sum;
    i64 res = 0;
    vector<pair<int, pi64> > anc;
    for (auto w: a) {
        int v = w.fi;
        pi64 z = w.se;
//        cerr << i << ' ' << b << ' ' << v << ' ' << z.fi << ' ' << z.se << ' ' << sum.fi << ' ' << sum.se << ' ' << res << '\n';
        vector<pair<int, pi64> > st;
        while (!anc.empty()) {
            int u = anc.back().fi;
            pi64 w = anc.back().se;
            int l = lca(u, v);
            if (l == u) break;
            sum = sum + w * (lcac[l] - lcac[u]);
            st.pb(mp(l, w));
            anc.pop_back();
        }
        while (!st.empty()) {
            if (anc.empty() || st.back().fi != anc.back().fi) anc.pb(st.back());
            else anc.back().se = anc.back().se + st.back().se;
            st.pop_back();
        }
        res = (res + cross(z, sum)) % P;
        anc.pb(mp(v, z));
        sum = sum + z * lcac[v];
    }
//    cerr << i << ' ' << b << " = " << t << '\n';
    int root = (i + off) >> b;
//    cerr << root << '\n';
    return (res * lcac[root] + solve(i, b - 1) + solve(i + (1 << (b - 1)), b - 1)) % P;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "rt", stdin);
#endif

    cin >> h;
    off = 1 << (h - 1);
    forn(i, 1 << (h - 1)) {
        cin >> perm[i];
        --perm[i];
    }

    int n = (1 << h) - 1;
    path[1] = 1;
    lcac[1] = 1;
    fore(i, 2, n) {
        path[i] = path[i / 2] * i % P;
        lcac[i] = lcac[i / 2] * deg(1LL * i * (i / 2) % P, -1) % P;
    }

    i64 ans = solve(0, h - 1);
    if (ans < 0) ans += P;
    cout << ans << '\n';

#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}
