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>
using namespace std;

#define llong long long 
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#define rand __rand
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());  // or mt19937_64
template<class T = int> T rand(T range = numeric_limits<T>::max()) { return (T)(rng() % range); }

#define CONCAT_(x, y) x##y/*{{{*/
#define CONCAT(x, y) CONCAT_(x, y)
#ifdef LOCAL_DEBUG   
int __db_level = 0;
bool __db_same_line = false;
#define clog cerr << string(!__db_same_line ? __db_level * 2 : 0, ' ')
struct debug_block {
    function<void()> fn;
    void print_name() { __db_same_line = true; fn(); clog << endl; __db_same_line = false;  }
    debug_block(function<void()> fn_): fn(fn_) { clog << "{ "; print_name(); ++__db_level; }
    ~debug_block() { --__db_level; clog << "} "; print_name(); }
};
#define DB(args...) debug_block CONCAT(dbbl, __LINE__)([=]{ clog << args; })
#define deb(...)  if (1) { (clog << "[" #__VA_ARGS__ "] = [" << __VA_ARGS__) << "]"; if (!__db_same_line) clog << endl; }
#else
#define clog if (0) cerr
#define DB(...)
#define deb(...)
#endif
template<class T>
ostream& operator,(ostream& out, const T& thing) { return out << ", " << thing; }
template<class U, class V>
ostream& operator<<(ostream& out, const pair<U, V>& p) { return (out << "(" << p.first, p.second) << ")"; }
template<class A, class B>
ostream& operator<<(ostream& out, const tuple<A, B>& t) { return (out << "(" << get<0>(t), get<1>(t)) << ")"; }
template<class A, class B, class C>
ostream& operator<<(ostream& out, const tuple<A, B, C>& t) { return (out << "(" << get<0>(t), get<1>(t), get<2>(t)) << ")"; }
template<class T> ostream& operator<<(ostream& out, const vector<T>& container) { 
    out << "{";
    if (len(container)) out << container[0];
    rep1(i, len(container) - 1) out, container[i];
    return out << "}";
}
template<class x> vector<typename x::value_type> $v(const x& a) { return vector<typename x::value_type>(a.begin(), a.end()); }
#define ptrtype(x) typename iterator_traits<x>::value_type
template<class u> vector<ptrtype(u)> $v(u a, u b) { return vector<ptrtype(u)>(a, b); }/*}}}*/
// ACTUAL SOLUTION BELOW ////////////////////////////////////////////////////////////

const int maxh = 19;
const int maxn = 1 << maxh;
const llong mod = (llong)1e9 + 7;

llong mpow(llong base, llong exp) {
    llong ans = 1;;
    for (; exp > 0; exp >>= 1) {
        if (exp & 1) (ans *= base) %= mod;
        (base *= base) %= mod;
    }
    return ans;
}

int h, n;
int p[maxn];

llong prod[maxn], iprod[maxn];
void cal_prod(int i = 1, int lv = h - 1) {
    prod[i] = i * prod[i / 2] % mod;
    iprod[i] = mpow(prod[i], mod - 2);
    if (lv == 0) return ;
    cal_prod(2 * i, lv - 1);
    cal_prod(2 * i + 1, lv - 1);
}

llong ans = 0;
llong cur_sum[maxn];

void dfs(int i = 1, int lv = h - 1) {
    DB(""; deb(i));
    if (lv == 0) return ;
    dfs(2 * i, lv - 1);
    dfs(2 * i + 1, lv - 1);
    
    rep(tail, (1 << (lv - 1))) {
        int cur = i << lv | tail;
        int other = p[cur];
        
        llong up_prod = prod[cur] * iprod[i / 2] % mod;
        deb(cur, other, up_prod, prod[cur], iprod[i / 2]);
        for (int par = other / 2; par > 0; par >>= 1) {
            llong down_prod = prod[other] * iprod[par / 2] % mod;
            deb(par, down_prod, up_prod * down_prod);
            cur_sum[par] += up_prod * down_prod % mod;
            if (cur_sum[par] >= mod) cur_sum[par] -= mod;
        }
    }
    
    clog << "seg" << endl;
    
    rep(tail, (1 << (lv - 1))) {
        int cur = (i << 1 | 1) << (lv - 1) | tail;
        int other = p[cur];
        
        llong up_prod = prod[cur] * iprod[i] % mod;
        deb(cur, other, up_prod, prod[cur], iprod[i / 2]);
        
        for (int par = other / 2, prev = other; par > 0; prev = par, par >>= 1) {
            llong down_prod = prod[other] * iprod[par] % mod;
            llong exluded_sum = (cur_sum[par] - cur_sum[prev] * par % mod + mod) % mod;
            llong cur_ans = up_prod * down_prod % mod * exluded_sum % mod;
            deb(par, down_prod, up_prod * down_prod, cur_ans);
            ans += cur_ans;
            if (ans >= mod) ans -= mod;
        }
    }
    rep(tail, (1 << (lv - 1))) {
        int cur = i << lv | tail;
        int other = p[cur];
        
        for (int par = other / 2; par > 0; par >>= 1) {
            cur_sum[par] = 0;
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> h;
    n = (1 << h);
    rep1(i, n / 2) {
        int x; cin >> x;
        p[i + n / 2 - 1] = x + n / 2 - 1;
    }
    
    prod[0] = iprod[0] = 1;
    cal_prod();
    dfs();
    cout << ans % mod;

    return 0;
}

// Remember:
// - Multitest? REFRESHING the data!!!
// - Constrains for each set of data may differs. Should NOT USE the same max constant (maxn)
//   for all of them.
// vim: foldmethod=marker

