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("unroll-loops")
#pragma GCC optimize("Ofast")
 
// hloya template v26
 
// ░░░░░░░▄▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄░░░░░░
// ░░░░░░█░░▄▀▀▀▀▀▀▀▀▀▀▀▀▀▄░░█░░░░░
// ░░░░░░█░█░▀░░░░░▀░░▀░░░░█░█░░░░░
// ░░░░░░█░█░░░░░░░░▄▀▀▄░▀░█░█▄▀▀▄░
// █▀▀█▄░█░█░░▀░░░░░█░░░▀▄▄█▄▀░░░█░
// ▀▄▄░▀██░█▄░▀░░░▄▄▀░░░░░░░░░░░░▀▄
// ░░▀█▄▄█░█░░░░▄░░█░░░▄█░░░▄░▄█░░█
// ░░░░░▀█░▀▄▀░░░░░█░██░▄░░▄░░▄░███
// ░░░░░▄█▄░░▀▀▀▀▀▀▀▀▄░░▀▀▀▀▀▀▀░▄▀░
// ░░░░█░░▄█▀█▀▀█▀▀▀▀▀▀█▀▀█▀█▀▀█░░░
// ░░░░▀▀▀▀░░▀▀▀░░░░░░░░▀▀▀░░▀▀░░░░
 
#include <bits/stdc++.h>
using namespace std;
 
bool dbg = 0;
  
clock_t start_time = clock();
#define current_time fixed<<setprecision(6)<<(ld)(clock()-start_time)/CLOCKS_PER_SEC
  
#define f first
#define s second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define sz(v) ((int)(v).size())
#define sqr(x) ((x) * (x))
 
#define ull unsigned long long
#define ll long long
#define ld long double
#define pii pair<int,int>
#define umap unordered_map<int, int>
 
#define files1 freopen("input.txt","r",stdin)
#define files2 freopen("output.txt","w",stdout)
#define files files1;files2
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0)
 
// #define endl '\n'
#define ln(i,n) " \n"[(i) == (n) - 1]
 
void bad(string mes = "NO"){cout << mes;exit(0);}
void bad(int mes){cout << mes;exit(0);}
 
template<typename T>
string bin(T x, int st = 2){
    string ans = "";
    while (x > 0){
        ans += char('0' + x % st);
        x /= st;
    }
    reverse(ans.begin(), ans.end());
    return ans.empty() ? "0" : ans;
}
 
mt19937_64 mt_rand(
    chrono::system_clock::now().time_since_epoch().count()
);
 
template<typename T1, typename T2> inline bool upmax(T1& a, T2 b) { return (a < b ? (a = b, true) : false); }
template<typename T1, typename T2> inline bool upmin(T1& a, T2 b) { return (b < a ? (a = b, true) : false); }
 
// inline int popcount(int x){
//     int count = 0;
//     __asm__ volatile("POPCNT %1, %0;":"=r"(count):"r"(x):);
//     return count;
// }
  
template<typename T>
T input(){
    T ans = 0, m = 1;
    char c = ' ';
  
    while (!((c >= '0' && c <= '9') || c == '-')) {
        c = getchar();
    }
  
    if (c == '-')
        m = -1, c = getchar();
    while (c >= '0' && c <= '9'){
        ans = ans * 10 + (c - '0'), c = getchar();
    }
    return ans * m;
}
 
template<typename T>
T gcd (T a, T b) { while (b) { a %= b; swap (a, b); } return a; }
  
template<typename T> void read(T& a) { a = input<T>(); }
template<typename T> void read(T& a, T& b) { read(a), read(b); }
template<typename T> void read(T& a, T& b, T& c) { read(a, b), read(c); }
template<typename T> void read(T& a, T& b, T& c, T& d) { read(a, b), read(c, d); }
 
const int inf = 1e9 + 20;
const short short_inf = 3e4 + 20;
const long double eps = 1e-12;
const int maxn = (int)3e5 + 3, base = 998244353;
const ll llinf = 2e18 + 5;
const int mod = 1e9 + 7;

int binpow (int a, int n) {
    int res = 1;
    while (n) {
        if (n & 1)
            res = 1ll * res * a % mod;
        a = 1ll * a * a % mod;
        n >>= 1;
    }
    return res;
}

int h, n_low;
int p[maxn];

int sum[maxn];
int ppref[maxn];
int ipref[maxn];

void dfs(int v, int l, int r) {
    ppref[v] = (1ll * ppref[v>>1] * v) % mod;
    ipref[v] = binpow(ppref[v], mod - 2);
    if (l == r) {
        return;
    }
    int m = (l + r) >> 1;
    dfs(v<<1, l, m);
    dfs(v<<1|1, m + 1, r);
}

int vertex_index(int i) {
    return i + (1 << h) - (1 << (h - 1));
}

int ans;

void solve(int v, int l, int r) {
    if (l == r) {
        return;
    }

    int m = (l + r) >> 1;

    for (int i = m + 1; i <= r; i++) {
        int lt1 = vertex_index(i);
        int lt2 = p[i];

        int val = 1ll * ppref[lt1] * ppref[lt2] % mod;
        for (int v2 = lt2; v2 > 0; v2 >>= 1) {
            sum[v2] += val;
            sum[v2] %= mod;
        }
    }

    for (int i = l; i <= m; i++) {
        int lt2 = p[i];
        int prod1 = 1ll * ppref[vertex_index(i)] % mod * ipref[v] % mod;

        for (int v2 = lt2; v2 > 1; v2 >>= 1) {
            int up = v2 >> 1;

            int paired_coeff = 1ll * ipref[v / 2] % mod * ipref[up / 2] % mod % mod;

            int paired = up * 2 == v2 ? up * 2 + 1 : up * 2;

            ans += 1ll * sum[paired] * paired_coeff % mod * ppref[lt2] % mod % mod * ipref[up] % mod * prod1 % mod;
            ans %= mod;

            // cout << 1ll * sum[paired] * paired_coeff % mod << endl;
            // cout << ans << endl;
        }
    }


    for (int i = m + 1; i <= r; i++) {
        int lt1 = vertex_index(i);
        int lt2 = p[i];

        int val = 1ll * ppref[lt1] * ppref[lt2] % mod;
        for (int v = lt2; v > 0; v >>= 1) {
            sum[v] -= val;
            sum[v] %= mod;
        }
    }

    solve(v<<1, l, m);
    solve(v<<1|1, m + 1, r);
}


int main() {
    // files1;
    fast_io;

    cin >> h;
    n_low = (1 << (h-1));

    for (int i = 0; i < n_low; i++) {
        cin >> p[i];
        p[i] += (1 << h) - 1 - (1 << (h - 1));
    }

    ppref[0] = ipref[0] = 1;
    dfs(1, 0, n_low - 1);

    solve(1, 0, n_low - 1);
    cout << ans;
    return 0;
}